Pairwise Node Swapping in Linked List

This operation involves swapping adjacent nodes in pairs rather than reversing the entire list. The approacch uses three pointers: prev pointing to the node before the current pair, first pointing to the first node of the pair, and second pointing to the second node. After swapping, second comes before first, and prev is updated to point to second, then moved to first to prepare for the next pair.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        previous = dummy
        
        while previous.next and previous.next.next:
            node1 = previous.next
            node2 = previous.next.next
            
            node1.next = node2.next
            node2.next = node1
            previous.next = node2
            previous = node1
            
        return dummy.next

Removing Nth Node From List End

Given the inability to directly determine a linked list's length, this solution employs two pointers. The fast pointer advances n steps ahead of slow. Both then move simultaneously until fast reaches the last node, at which point slow points to the node preceding the one to be removed.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        
        for i in range(n):
            fast = fast.next
            
        while fast.next:
            fast = fast.next
            slow = slow.next
            
        slow.next = slow.next.next
        return dummy.next

Finding Intersection Node of Two Linked Lists

By having each pointer traverse both lists (its own list first, then the other list), both pointers coverr the same total distance. This equalizes path lengths and ensures they meet at the intersection node or at the end if no intersection exists.

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        pointerA, pointerB = headA, headB
        
        while pointerA != pointerB:
            pointerA = pointerA.next if pointerA else headB
            pointerB = pointerB.next if pointerB else headA
            
        return pointerA

Detecting Cycle Start in Linked List

For cycle detection, use fast and slow pointers where fast moves two steps per iteration and slow moves one. If they meet, a cycle exists. To find the cycle entrance, reset one pointer to the head after detection and advance both at one step per iteration - their meeting point is the cycle entrance.

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
                
        return None