Detect Cycle in Linked List
Move one pointer one step and another pointer two steps at a time. If they ever meet, there is a cycle; if the fast pointer reaches the end, the list is acyclic.
Return whether a linked list contains a cycle.
Tagged with linked-list
5 cards
Find Middle of Linked List
Advance a slow pointer by one step and a fast pointer by two steps. When the fast pointer reaches the end, the slow pointer will be at the middle.
Return the middle node of a singly linked list.
Merge Two Sorted Linked Lists
Use a dummy head and repeatedly attach the smaller current node from either list. When one list runs out, append the remaining nodes from the other list.
Merge two sorted linked lists and return the head of the merged list.
Remove Nth Node From End
Use a dummy node, move the fast pointer n steps ahead, then move both fast and slow together until fast reaches the end. The slow pointer will be just before the node to remove.
Remove the nth node from the end of a linked list and return the head.
Reverse Linked List
Walk the list node by node, reverse each next pointer, and move the window forward until the list is exhausted.
Reverse a singly linked list and return the new head.