Swapping Adjacent Nodes in a Linked List

The core idea involves using a dummy head node to simplify edge cases and ensure consistent operations on the first node. When swapping node pairs, careful attention must be paid to preserving references before reassigning pointers.

Key considerations:

• Use a dummy head node to eliminate special treatment for the head
• Store referecnes to all nodes involved before updating pointers
• Maintain correct order when updating pointers to avoid losing node references

type ListNode struct {
    Val  int
    Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    
    dummy := &ListNode{}
    dummy.Next = head
    
    current := dummy
    
    for current.Next != nil && current.Next.Next != nil {
        first := current.Next
        second := current.Next.Next
        
        // Perform the swap
        current.Next = second
        first.Next = second.Next
        second.Next = first
        
        // Move to next pair
        current = current.Next.Next
    }
    
    return dummy.Next
}

Removing the Nth Node from the End

This problem requires finding and removing a node at a specific position from the end. The optimal approach uses a sliding window technique with two pointers.

Key considerations:

• Use a dummy head to handle edge cases uniformly
• Create a fixed gap between fast and slow pointers
• Move fast pointer n+1 steps ahead to locate the predecessor of the target node
• The value of n ranges from 1 to the list length

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    
    fast := dummy
    slow := dummy
    
    // Move fast pointer n+1 steps ahead
    gap := n + 1
    for gap > 0 && fast != nil {
        fast = fast.Next
        gap--
    }
    
    // Move both pointers until fast reaches end
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // Remove the target node
    slow.Next = slow.Next.Next
    
    return dummy.Next
}

Finding Intersection of Two Linked Lists

Two linked lists intersect when they share the same node reference (not just the same value). If they intersect, they must align at their tails.

Key observations:

• Compare node references, not values
• Aligned tails imply intersection
• Calculate lengths and align the starting positions

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // Calculate lengths
    ptrA := headA
    ptrB := headB
    lenA, lenB := 0, 0
    
    for ptrA != nil {
        lenA++
        ptrA = ptrA.Next
    }
    
    for ptrB != nil {
        lenB++
        ptrB = ptrB.Next
    }
    
    // Reset pointers
    ptrA = headA
    ptrB = headB
    
    // Ensure ptrA is the longer list
    if lenA < lenB {
        ptrA, ptrB = ptrB, ptrA
        lenA, lenB = lenB, lenA
    }
    
    // Align to same starting position from end
    diff := lenA - lenB
    for diff > 0 {
        ptrA = ptrA.Next
        diff--
    }
    
    // Find intersection point
    for ptrA != nil {
        if ptrA == ptrB {
            return ptrA
        }
        ptrA = ptrA.Next
        ptrB = ptrB.Next
    }
    
    return nil
}

Detecting Cycle Start in Linked List

Using fast and slow pointers, a cycle can be detected when they meet. The mathematical relationship between distances allows finding the cycle entry point.

Mathematical derivation:

• When fast and slow meet: fast travels twice the distance of slow
• Let x = distance from head to cycle start
• Let y = distance from cycle start to meeting point
• Let z = cycle length
• Equation: x + y = (n-1)z + z, simplifying to x = (n-1)(y+z) + z
• Special case when n=1: x = z

func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    
    // Find meeting point
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        
        if fast == slow {
            // Cycle detected, find entry point
            start := head
            meet := fast
            
            for start != meet {
                start = start.Next
                meet = meet.Next
            }
            
            return start
        }
    }
    
    return nil
}

Key Takeaways

Linked lists offer efficient insertions and deletions but slower random access compared to arrays. Important considerations:

• Dummy head nodes simplify operations at the head position
• In Go, initialization requires explicit nil assignment after declaration
• Continuous memory allocation is avoided, providing better memory utilization
• Pointer manipulation requires careful ordering to prevent losing references