• All a linked list really is is the head node (which points to the next node, and so on).
• To reverse a linked list, just need to remember to store next and update prev and curr pointers at each iteration:
• nxt = curr.next
• curr.next = prev
• prev = curr
• curr = nxt
• To recursively reverse:
• base case is null node or null node.next
• Deleting a node n is just setting the references to skip n: prev.next = n.next;
• Can also delete a curr node even without a prev pointer: curr.data = curr.next.data; curr.next = curr.next.next;
Basically, copy (and overwrite) next's data to curr and delete next.
• Just make sure to check for the null pointer (!!) and be aware of the head pointer.
• Linked lists offer easy modification but non-existent random access.
• An important technique is the "runner" one:
• Have two pointers iterating through the list, with one pointer either ahead by a fixed amount or actually moving faster.
• For example, to determine the midpoint of a linked list, have two pointers such that one of them jumps 2 nodes at once and the other just 1. When the fast pointer hits the end, the slow one will be in the middle of the list.
• To determine if a linked list has a cycle, do the same thing where 1 pointer moves ahead 2 nodes at a time. If there's a cycle, the runner will eventually equal the normal curr node. If not, will hit null node.
• https://www.wikiwand.com/en/Cycle_detection#/Tortoise_and_hare
• slow = fast = head
• while fast and fast.next:
• slow = slow.next
• fast = fast.next.next
• if slow == fast: return True
• return False
• then, once fast = slow, reset slow to head of list, and move forward both pointers 1 at a time. once they equal again, that's the start of the cycle. then move the fast pointer 1 at a time, once they equal for the 3rd time, that's the length of the cycle
• can also use this to detect duplicates in an array given certain constraints
• http://keithschwarz.com/interesting/code/?dir=find-duplicate
• https://leetcode.com/problems/find-the-duplicate-number/description/
• slow = fast = head
• has_cycle = False
• while fast and fast.next:
• slow = slow.next
• fast = fast.next.next
• if slow == fast:
• has_cycle = True
• break
• if not has_cycle: return None
• # the point where they meet again, resetting slow to head, is the cycle start
• fast = fast.next
• or alternatively, if don't need the start index and just want cycle length, move fast 1 node at a time until hits slow again
• A fixed amount (also called the stick approach) use case would be to determine the start of a cycle if you know the length of the cycle.
• Recursion can often help.
• Example problems and model code:
• Sort linked list using O(1) space and O(n log n) time:
https://leetcode.com/problems/sort-list/description/
• # base case
• # get middle (if even, get 1st middle)
• slow = fast = head
• while fast.next and fast.next.next:
• slow = slow.next
• fast = fast.next.next
• # split list in two and sort halves
• h2 = slow.next
• slow.next = None