Problems

kth node from end

Problem Statement: Given a linked list find the kth node from the end.

Approach:
Use two pointers. Move one pointer k nodes ahead and then move both pointers until the first pointer reaches the end of the list. The second pointer will be at the kth node from the end.

public Node kthFromEnd(Node head, int k) {
    Node first = head;
    Node second = head;

    for (int i = 0; i < k; i++) {
        if (first == null) return null; // k is greater than the length of the list
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}

---

Check is linked list is cyclic

Problem Statement: Check if the given linked list contain a cycle.

Approach:
Use two pointers. Move one pointer one step at a time and the other pointer two steps at a time. If they meet, the list is cyclic.
If there is a cycle, once the 2 pointers enter the cycle, they will meet at some point. If there is no cycle, the fast pointer will reach the end of the list.
Also called Floyd's Cycle Detection Algorithm.

public boolean hasCycle(Node head) {
    if (head == null) return false;
    Node slow = head;
    Node fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true; // Cycle detected
    }
    return false; // No cycle
}

Extension Find the start of the cycle. After finding the cycle, keep one pointer at the start of the list and move both pointers one step at a time. The point where they meet is the start of the cycle.

---

Find intersection point of two LL

Problem Statement: Find the intersection node of two linked lists.

Approach:

• Find the length of both lists \(l_1, l_2\).
• Find the difference in lengths \(d = l_1 - l_2\).
• Move the longer list by d.
• Move both lists one step at a time until they meet. The point where they meet is the intersection point.

public Node getIntersection(Node head1, Node head2) {
    int len1 = getLength(head1);
    int len2 = getLength(head2);

    int d = Math.abs(len1 - len2);
    if(len1 < len2) swap(head1, head2);

    for (int i = 0; i < d; i++) {
        head1 = head1.next;
    }

    while (head1 != null && head2 != null) {
        if (head1 == head2) return head1; // Intersection point
        head1 = head1.next;
        head2 = head2.next;
    }
    return null; // No intersection
}

---

Random pointer & cloning

Problem Statement: A linked list consists of both next and random pointers. Clone this linked list.

Approach:

• A new node is inserted after each node in the original list.
• The next pointer of the new node points to the next node in the original list.
• Make node\(\rightarrow\)next\(\rightarrow\)random = node\(\rightarrow\)random\(\rightarrow\)next.
• We are pointing clone node's random to clone of the original node's random.
• Finally, we separate the two lists.

class Node {
    int val;
    Node next;
    Node random;

    Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public Node cloneList(Node head) {
    if (head == null) return null;

    // Step 1: Create a copy of each node and insert it after the original node
    Node curr = head;
    while (curr != null) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }

    // Step 2: Set the random pointers for the copied nodes
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }

    // Step 3: Separate the copied nodes from the original list
    curr = head;
    Node dummyHead = new Node(0);
    Node copyCurr = dummyHead;

    while (curr != null) {
        copyCurr.next = curr.next;
        curr.next = curr.next.next; 
        copyCurr = copyCurr.next;
        curr = curr.next;
    }

    return dummyHead.next; // Return the head of the copied list
}

---

Reorder

Problem Statement: Given {\(A_1, A_2 \dots A_n\)} reorder to {$A_1, A_n, A_2, A_{n-1} \dots $}

Approach:

• Find middle.
• Reverse second half.
• Inplace merge first and second half.

---

Delete consecutive nodes that sum to zero

Problem Statement: Given a linked list, delete all consecutive nodes that sum to zero.

Approach:
Record accumulated sum from head. sum(i) == sum(j) => sum within (i,j] is 0

public Node removeZeroSumSublists(Node head) {
    Map<Integer, Node> map = new HashMap<>();
    Node dummy = new Node(0);
    dummy.next = head;
    map.put(0, dummy);

    int sum = 0;
    Node curr = head;

    while (curr != null) {
        sum += curr.val;
        if (map.containsKey(sum)) {
            Node prev = map.get(sum);
            prev.next = curr.next; // Remove the nodes between prev and curr
        } else {
            map.put(sum, curr);
        }
        curr = curr.next;
    }

    return dummy.next; // Return the modified list
}