PU Data Structure: Linked List

Merge:

• 2 Add Two Numbers (perfect) [dummy + carry]
• 21 Merge Two Sorted Lists (perfect) [dummy]
• 23 Merge K Sorted Lists (perfect) [dummy + heapq/merge sort]

recursive

• 24 Swap Nodes in Pairs (perfect) [recursive, dummy + reverse-unpacking]

Reverse [use upacking] [keep head unchange, keep tail unchange, put the node behind tail to the position behind head]

• 24 Swap Nodes in Pairs (perfect) [recursive, dummy + reverse-unpacking]
• 25 Reverse Nodes in k-Group (perfect) [dummy + iterate + reverse-unpacking]
• 92 Reverse Linked List II (perfect) [dummy + reverse-unpacking]
• 143 Reorder List (perfect) [two-pointers + reverse]
• 206 Reverse Linked List (perfect) [no dummy, only unpacking, be careful about the unpacking order]
  • Reverse Linked List I and II is totally different.
• 234 Palindrome Linked List (perfect) [two-pointers + reverse]
• 369 Plus One Linked List (perfect) [reverse or special]
• 445 Add Two Numbers II (perfect) [reverse or extra space and then reverse]

Rotate [connect tail to head]

• 61 Rotate List (perfect) [test tail.next instead of tail]

Remove

• 19 Remove Nth Node From End of List (perfect) [dummy + two pointers]
• 83 Remove Duplicates from Sorted List (perfect)
• 85 Remove Duplicates from Sorted List II (perfect) [dummy]
• 203 Remove Linked List Elements (perfect) [dummy]
• 237 Delete Node in a Linked List (perfect)

Two Pointers

• 19 Remove Nth Node From End of List (perfect) [dummy + two pointers]
• 109 Convert Sorted List to Binary Search Tree (perfect) [fast start from head.next.next]
• 141 Linked List Cycle (perfect) [start from different node]
• 142 Linked List Cycle II (perfect) [both start from head]
• 143 Reorder List (perfect) [two-pointers + reverse]
• 160 Intersection of Two Linked Lists (perfect) [connect to each other]
• 234 Palindrome Linked List (perfect) [two-pointers + reverse]

Divide

• 86 Partition List (perfect) [dummy]

Sort:

• 147 Insertion Sort List (perfect) [dummy]
• 148 Sort List (perfect) [recursive + mergesort or dummy + mergesort]

Other:

• 138 Copy List with Random Pointer (perfect) [hashtable or special]
• 328 Odd Even Linked List (perfect)
• 382 Linked List Random Node (perfect)
• 369 Plus One Linked List (perfect) [reverse or special]
• 379 Design Phone Directory