Pairwise Node Swapping in Linked List

Given a linked list, swap every two adjacnet nodes and return the modified list's head. Node values must not be altered; only node positions can be chenged.

Example:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Solution: Use three pointers to manage node connections during swapping.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            current.next = second;
            first.next = second.next;
            second.next = first;
            current = current.next.next;
        }
        return dummy.next;
    }
}

Removing Nth Node from End of Linked List

Delete the nth node counting from the end of a linked list and return the updated head.

Example:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Solution: Calculate list length first, then traverse to the node preceding the target.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode current = head;
        int length = 0;
        while (current != null) {
            length++;
            current = current.next;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode pointer = dummy;
        for (int i = 0; i < length - n; i++) {
            pointer = pointer.next;
        }
        pointer.next = pointer.next.next;
        return dummy.next;
    }
}

Finding Intersection Node of Two Linked Lists

Given two linked list heads, return the node where they intersect. If no intersection exists, return null.

Example:

Input: listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
Output: Intersected at node with value 8

Solution: Equalize traversal starting points by accounting for length differences.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        int lenA = 0, lenB = 0;
        while (p1 != null) {
            lenA++;
            p1 = p1.next;
        }
        while (p2 != null) {
            lenB++;
            p2 = p2.next;
        }
        
        p1 = headA;
        p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        
        while (p1 != null && p2 != null) {
            if (p1 == p2) return p1;
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
}

Detecting Cycle Start in Linked List

Return the node where a cycle begins in a linked list. If no cycle exists, return null.

Example:

Input: head = [3,2,0,-4], cycle starts at node with value 2
Output: Node with value 2

Solution: Use fast and slow pointers to detect cycle, then find cycle start.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                ListNode start = head;
                ListNode meeting = slow;
                while (start != meeting) {
                    start = start.next;
                    meeting = meeting.next;
                }
                return start;
            }
        }
        return null;
    }
}