Problem: 24. Swap Nodes in Pairs

To swap two adjacent nodes, we need a pointer standing just before the pair. A dummy sentinel node placed before the head simplifies edge cases. The traversal pointer curr starts at the sentinel. Swapping involves rerouting next pointers in three steps while preserving references that might be lost.

The loop condition ensures both nodes exist: while (curr->next != nullptr && curr->next->next != nullptr). The order of checks is critical to avoid null dereferences when the list length is odd or even.

Swap procedure:

1. Save the first node and the node after the pair (the third node) before breaking links.
2. Reassign pointers: curr->next points to the second node, the second node’s next points to the first, and the first node’s next points to the saved third node.
3. Advance curr two steps forward.

ListNode* swapPairs(ListNode* head) {
   ListNode sentinel(0);
   sentinel.next = head;
   ListNode* curr = &sentinel;
   while (curr->next != nullptr && curr->next->next != nullptr) {
       ListNode* first  = curr->next;
       ListNode* rest   = curr->next->next->next;  // node after the swapped pair
       curr->next = curr->next->next;
       curr->next->next = first;
       first->next = rest;
       curr = curr->next->next;
   }
   return sentinel.next;
}
 

Removing the N-th Node from the End

Problem: 19. Remove Nth Node From End of List

The two‑pointer technique eliminates the need for reversing the list. A fast pointer moves n+1 steps ahead, ensuring that when it reaches the end, the slow pointer sits just before the node to be deleted. Deleting the target node then follows the standard snipping procedure.

ListNode* removeNthFromEnd(ListNode* head, int n) {
   ListNode sentinel(0);
   sentinel.next = head;
   ListNode *fast = &sentinel, *slow = &sentinel;
   int steps = n + 1;
   while (steps--) fast = fast->next;
   while (fast) {
       fast = fast->next;
       slow = slow->next;
   }
   ListNode* toDelete = slow->next;
   slow->next = toDelete->next;
   delete toDelete;
   return sentinel.next;
}
 

Finding the Intersectino of Two Linked Lists

Problem: Intersection of Two Linked Lists LCCI

Two lists may merge at a common node (by reference, not value). After aligning their tail ends, walk both pointers simultaneously until they meet.

1. Compute lengths of both lists.
2. Advance the longer list’s pointer by the length difference so both pointers start equidistant from the tail.
3. Traverse together until the pointers reference the same node or reach the end.

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
   ListNode *pa = headA, *pb = headB;
   int lenA = 0, lenB = 0;
   while (pa) { lenA++; pa = pa->next; }
   while (pb) { lenB++; pb = pb->next; }
   pa = headA; pb = headB;
   // Make pa the head of the longer list
   if (lenB > lenA) {
       std::swap(lenA, lenB);
       std::swap(pa, pb);
   }
   int diff = lenA - lenB;
   while (diff--) pa = pa->next;
   while (pa) {
       if (pa == pb) return pa;
       pa = pa->next;
       pb = pb->next;
   }
   return nullptr;
}
 

Detecting a Cycle and Locating Its Entry

Problem: 142. Linked List Cycle II

A fast pointer (two steps) and a slow pointer (one step) detect a cycle if they meet. To find the entry point, we use the relationship: after they meet, a pointer starting from the head and another from the meeting point will converge exactly at the cycle’s entry, due to the distance equations:

• Let the head‑to‑entry distance be x, entry‑to‑meeting point be y, and the remaining back‑to‑entry portion be z.
• When fast catches slow: slow = x + y, fast = x + y + n(y+z), and 2(x+y) = x + y + n(y+z) ⇒ x = (n-1)(y+z) + z.
• This shows that starting two pointers from the head and the meeting point will make them meet at the cycle entry.

ListNode* detectCycle(ListNode* head) {
   ListNode *fast = head, *slow = head;
   while (fast && fast->next) {
       slow = slow->next;
       fast = fast->next->next;
       if (slow == fast) {   // cycle confirmed
           ListNode* entry1 = fast;
           ListNode* entry2 = head;
           while (entry1 != entry2) {
               entry1 = entry1->next;
               entry2 = entry2->next;
           }
           return entry2;    // entry of the cycle
       }
   }
   return nullptr;
}