Swapping Adjacent Nodes in Pairs

To exchange every two consecutive nodes in a singly linked list:

• Introduce a dummy node to simplify edge cases.
• Use a pointer to traverse and perform swaps iterative.
• Ensure loop termination checks prevent null dereferencing.

class Node:
    def __init__(self, value=0, nxt=None):
        self.value = value
        self.nxt = nxt

class Solver:
    def pairSwap(self, head):
        stub = Node(nxt=head)
        curr = stub
        while curr.nxt and curr.nxt.nxt:
            first = curr.nxt
            second = first.nxt
            first.nxt = second.nxt
            second.nxt = first
            curr.nxt = second
            curr = first
        return stub.nxt

Removing the N-th Node from List End

Efficient removal from the tail without knowing length:

• Create a santinel node to handle head deletion uniformly.
• Advance a leading pointer N steps ahead.
• Move both leader and follower until leader reaches end; follower will precede target.

class Node:
    def __init__(self, value=0, nxt=None):
        self.value = value
        self.nxt = nxt

class Solver:
    def deleteFromEnd(self, head, k):
        guard = Node(nxt=head)
        lead = lag = guard
        step = 0
        while lead.nxt:
            lead = lead.nxt
            step += 1
            if step > k:
                lag = lag.nxt
        lag.nxt = lag.nxt.nxt
        return guard.nxt

Finding Intersection of Two Lists

Locate the first common node of two singly linked lists:

• Compute lengths of both lists.
• Offset the longer list's start so remaining nodes match in count.
• Advance both poinetrs together; equality indicates intersection.

class Node:
    def __init__(self, value=0, nxt=None):
        self.value = value
        self.nxt = nxt

class Solver:
    def findJoinNode(self, h1, h2):
        p1, p2 = h1, h2
        len1 = len2 = 0
        temp = h1
        while temp:
            len1 += 1
            temp = temp.nxt
        temp = h2
        while temp:
            len2 += 1
            temp = temp.nxt
        diff = abs(len1 - len2)
        if len1 < len2:
            p1, p2 = h2, h1
        for _ in range(diff):
            p1 = p1.nxt
        while p1 and p2:
            if p1 is p2:
                return p1
            p1 = p1.nxt
            p2 = p2.nxt
        return None

Detecting Cycle Start in Linked List

Identify presence and entry point of a cycle using two-pointer technique:

• Move one pointer at double speed; another at single speed.
• If they meet, a cycle exists.
• Reset one pointer to head, advance both at same pace; meeting point is cycle entrance.

Reasoning: Let distance from head to cycle start be a, start to meeting point be b, and meeting point to start around cycle be c. When slow enters cycle, fast has traveled a+b; fast laps cycle n times: a+b = n(b+c). For n=1, a = c. Thus advancing equal steps from meeting point and head converges at cycle entry.

class Node:
    def __init__(self, value=0, nxt=None):
        self.value = value
        self.nxt = nxt

class Solver:
    def locateCycleStart(self, head):
        slow = fast = head
        while fast and fast.nxt and fast.nxt.nxt:
            slow = slow.nxt
            fast = fast.nxt.nxt
            if slow is fast:
                ptr1 = head
                ptr2 = slow
                while ptr1 is not ptr2:
                    ptr1 = ptr1.nxt
                    ptr2 = ptr2.nxt
                return ptr1
        return None