Linked lists are fundamental data structures that support various manipulations, including reordering elements, removing specific nodes, identifying common elements across lists, and detecting structural patterns like cycles. This document explores several common and important linked list problems, demonstrating efficient algorithmic approaches for each.

Sawpping Nodes in Pairs

The task is to swap every two adjacent nodes in a linked list. For instance, a list 1->2->3->4 would become 2->1->4->3. A common strategy involves using a dummy node to simplify operations at the head of the list and a pointer to track the node before the pair being swapped.

Consider the following Java implementation:

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // Create a dummy node to handle potential head changes
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy; // 'current' points to the node before the pair to be swapped

        while (current.next != null && current.next.next != null) {
            ListNode firstNode = current.next;
            ListNode secondNode = current.next.next;

            // Perform the swap operation
            firstNode.next = secondNode.next; // The original firstNode now points past the original secondNode
            secondNode.next = firstNode;      // The original secondNode now points to the original firstNode
            current.next = secondNode;        // The node before the pair now points to the original secondNode (which is now first)

            // Advance 'current' to the original firstNode, which is now the second node of the swapped pair
            // This sets 'current' up to be before the next pair
            current = firstNode;
        }

        return dummy.next;
    }
}

Removing the Nth Node From the End of a List

To remove the Nth node from the end of a singly linked list, a robust approach uses two pointers, often referred to as fast and slow. The fast pointer is advanced N+1 steps ahead of the slow pointer. This gap ensures that when the fast pointer reaches the end of the list, the slow pointer is positioned just before the node that needs to be removed.

Here's an example in Java:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(0); // A dummy node simplifies edge cases, especially removing the head
        sentinel.next = head;

        ListNode fastPtr = sentinel;
        ListNode slowPtr = sentinel;

        // Advance 'fastPtr' (N + 1) steps. The extra step ensures 'slowPtr' stops before the target node.
        for (int i = 0; i <= n; i++) {
            // In typical competitive programming, 'n' is guaranteed to be valid.
            // If not, additional checks for fastPtr == null would be needed.
            fastPtr = fastPtr.next;
        }

        // Move both pointers until 'fastPtr' reaches the end of the list (becomes null)
        while (fastPtr != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next;
        }

        // 'slowPtr' is now at the node preceding the one to be removed.
        // Update its 'next' pointer to bypass the target node.
        if (slowPtr.next != null) {
            slowPtr.next = slowPtr.next.next;
        }

        return sentinel.next; // Return the head of the modified list
    }
}

Finding the Intersection Point of Two Linked Lists

Determining the intersection point of two singly linked lists can be achieved efficiently without first calculating their lengths. A clever two-pointer technique involves having each pointer traverse both lists. If an intersection exists, the pointers will eventually meet at the intersection node. If no intersection exists, both pointers will simultaneously become null.

The core idea is: ListA + ListB will have the same total path length as ListB + ListA. If they intersect, they will meet on this combined path.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null; // No intersection possible if either list is empty
        }

        ListNode pointerA = headA;
        ListNode pointerB = headB;

        // Iterate until pointers meet or both become null (no intersection)
        while (pointerA != pointerB) {
            // If pointerA reaches the end of list A, redirect it to headB.
            // Otherwise, advance it in list A.
            pointerA = (pointerA == null) ? headB : pointerA.next;

            // If pointerB reaches the end of list B, redirect it to headA.
            // Otherwise, advance it in list B.
            pointerB = (pointerB == null) ? headA : pointerB.next;
        }

        return pointerA; // This will be the intersection node or null if no intersection
    }
}

Detecting the Cycle's Starting Node in a Linked List

Identifying the starting node of a cycle in a linked list is a classic problem often solved using Floyd's Tortoise and Hare algorithm. This algorithm proceeds in two phases:

1. Cycle Detection: Two pointers, a slow one (tortoise) moving one step at a time and a fast one (hare) moving two steps at a time, are used. If they ever meet, a cycle exists.
2. Cycle Start Identification: Once a cycle is detected (i.e., tortoise == hare), one pointer is reset to the head of the list. Both tortoise and this new pointer then advance one step at a time. The point where they meet again is the beginning of the cycle.

This works because when the tortoise and hare meet, the distance from the list's head to the cycle's entry point is equal to the distance from the meeting point to the cycle's entry point (traversed clockwise).

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null; // A cycle requires at least two nodes
        }

        ListNode tortoise = head; // Moves one step at a time
        ListNode hare = head;     // Moves two steps at a time

        // Phase 1: Detect if a cycle exists
        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare = hare.next.next;

            if (tortoise == hare) { // Cycle detected (pointers meet)
                // Phase 2: Find the entry point of the cycle
                ListNode entryPoint = head; // Start a new pointer from the head
                while (entryPoint != tortoise) {
                    entryPoint = entryPoint.next;
                    tortoise = tortoise.next;
                }
                return entryPoint; // The meeting point is the cycle's entry
            }
        }

        return null; // No cycle found in the list
    }
}