LinkedList Problem Solving

A guide to solving classic LinkedList problems using the Slow & Fast Pointer technique.

Types of Linked Lists

1. Singly Linked List

The simplest type. Each node contains data and a pointer to the next node in the sequence. Traversal is only possible in one direction (forward).


class Node {
    int data;
    Node next;

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

2. Doubly Linked List

Each node contains data, a pointer to the next node, and a pointer to the previous node. This allows for traversal in both forward and backward directions.


class Node {
    int data;
    Node next;
    Node prev;

    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

3. Circular Linked List

A variation where the last node's `next` pointer points back to the first node (the head) instead of `null`, forming a circle. It can be singly or doubly circular.

The code below shows how you might create a simple circular linked list where the last node points back to the head.


public class CircularLinkedList {
    public Node createCircularList() {
        // Create nodes
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);

        // Link them up
        head.next = second;
        second.next = third;
        third.next = fourth;
        
        // Make it circular: the last node points back to the head
        fourth.next = head; 

        return head;
    }
}

Slow & Fast Pointer Problems

1. Detect a Loop in a Linked List

Algorithm: Use two pointers, `slow` and `fast`. Move `slow` by one step and `fast` by two steps. If the linked list has a loop, the `fast` pointer will eventually meet the `slow` pointer. If `fast` reaches `null` or `fast.next` is `null`, there is no loop.

Show Code

Show Dry Run


class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true; // Loop detected
            }
        }
        return false; // No loop
    }
}

Example: 1 -> 2 -> 3 -> 4 -> 5 -> (points back to 3)

Step	Slow Pointer	Fast Pointer	Comment
Start	1	1	Both start at the head.
1	2	3	Slow moves 1, Fast moves 2.
2	3	5	Slow moves 1, Fast moves 2.
3	4	4	Slow is at 4, Fast moves from 5 to 3, then to 4. They meet.
Since `slow` and `fast` have met, a loop is detected.

2. Find the Starting Point of a Cycle

Algorithm: First, detect the loop using the slow and fast pointer method as above. Once they meet, keep one pointer (`slow`) at the meeting point and move the other pointer (`fast`) to the head of the list. Now, move both pointers one step at a time. The point where they meet again is the starting node of the loop.

Show Code

Show Dry Run


public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (hasCycle) {
            fast = head; // Reset one pointer to the head
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow; // The meeting point is the start of the cycle
        }
        
        return null;
    }
}

Example: 1 -> 2 -> 3 -> 4 -> 5 -> (points back to 3). Loop starts at node 3.

Part 1: Detect Loop - We know from the previous problem they meet at node 4.

Part 2: Find Start

Step	Slow Pointer (starts at meeting point)	Fast Pointer (starts at head)	Comment
Start	4	1	Reset fast to head.
1	5	2	Move both by 1.
2	3	3	Move both by 1. They meet at 3.
The meeting point, node 3, is the start of the cycle.

3. Find Intersection Point of Two Lists (Y-Shape)

Algorithm: This doesn't use the traditional slow/fast pointer speed difference but a similar "two pointer" traversal idea. Use two pointers, `ptrA` for list A and `ptrB` for list B. Traverse both lists. When `ptrA` reaches the end of list A, redirect it to the head of list B. Similarly, when `ptrB` reaches the end of list B, redirect it to the head of list A. If the lists intersect, the two pointers will meet at the intersection node. If they don't intersect, they will both become `null` at the same time.

Show Code

Show Dry Run


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode ptrA = headA;
        ListNode ptrB = headB;

        while (ptrA != ptrB) {
            // If ptrA reaches the end of its list, move it to the head of B
            ptrA = (ptrA == null) ? headB : ptrA.next;
            
            // If ptrB reaches the end of its list, move it to the head of A
            ptrB = (ptrB == null) ? headA : ptrB.next;
        }
        // They will either meet at the intersection or at null (if no intersection)
        return ptrA;
    }
}

Example:
List A: 4 -> 1 -> 8 -> 4 -> 5
List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
They intersect at node with value 1.

Step	ptrA Position	ptrB Position
Start	A:4	B:5
1	A:1	B:6
2	A:8	B:1
3	A:4	A:8 (ptrB reached end of B, moves to head of A)
4	A:5	A:4
5	B:5 (ptrA reached end of A, moves to head of B)	A:5
6	B:6	B:6 (ptrA is at B:6, ptrB is at A:5->next which is B:6)
7	B:1	B:1
The pointers meet at the node with value 1. This is the intersection.

4. Add Two Numbers in a Linked List

Algorithm: This problem is a classic list traversal problem, not typically a slow/fast pointer one, but essential for linked list practice. You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order. Traverse both lists simultaneously, adding the corresponding digits along with a `carry` from the previous step. Create a new linked list to store the result.

Show Code

Show Dry Run


public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            int digit = sum % 10;
            
            current.next = new ListNode(digit);
            current = current.next;
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        return dummyHead.next;
    }
}

Example: l1 = 2 -> 4 -> 3 (342), l2 = 5 -> 6 -> 4 (465). Result should be 7 -> 0 -> 8 (807).

Step	l1 Node	l2 Node	Carry In	Sum	Digit	Carry Out	Result List
1	2	5	0	2+5+0 = 7	7	0	7
2	4	6	0	4+6+0 = 10	0	1	7 -> 0
3	3	4	1	3+4+1 = 8	8	0	7 -> 0 -> 8
Final result: 7 -> 0 -> 8

5. Josephus Problem (Circular Linked List)

Problem: Given the total number of people n standing in a circle, every second person is eliminated until only one person remains. Find the position of the last remaining person.

Approach: We'll use a circular linked list to simulate the elimination process. Each node represents a person, and we'll eliminate every second node until only one remains.


import java.util.Scanner;

class Main {
    private static class MyCircularList {
        private class Node {
            int value;
            Node next;

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

        Node head;
        Node tail;

        public MyCircularList() {
            head = null;
            tail = null;
        }

        public void insertAtEnd(int val) {
            Node newNode = new Node(val);
            if (this.head == null) {
                this.head = newNode;
                this.tail = newNode;
            } else {
                this.tail.next = newNode;
                this.tail = newNode;
            }
            this.tail.next = head; // Make it circular
        }

        public void solution() {
            if (head == null) return;
            
            Node current = head;
            while (current.next != current) {
                // The next node will be eliminated
                Node nodeToRemove = current.next;
                
                // If we're about to remove the head, update the head
                if (nodeToRemove == head) {
                    head = nodeToRemove.next;
                }
                
                // Skip the node to be removed
                current.next = nodeToRemove.next;
                
                // Move to the next person (the one after the removed node)
                current = current.next;
            }
            
            System.out.println("The last remaining person is at position: " + current.value);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of test cases: ");
        int t = sc.nextInt();
        
        while (t-- > 0) {
            System.out.print("Enter number of people in the circle: ");
            int n = sc.nextInt();
            
            MyCircularList list = new MyCircularList();
            for (int i = 1; i <= n; i++) {
                list.insertAtEnd(i);
            }
            
            System.out.print("For " + n + " people, ");
            list.solution();
        }
        sc.close();
    }
}

Dry Run Example (n = 5):

Initial circle: 1 → 2 → 3 → 4 → 5 → (back to 1)

Elimination steps:

Start at 1, eliminate 2: 1 → 3 → 4 → 5 → (back to 1)
Next at 3, eliminate 4: 1 → 3 → 5 → (back to 1)
Next at 5, eliminate 1: 3 → 5 → (back to 3)
Next at 3, eliminate 5: Only 3 remains

The last remaining person is at position: 3

Time Complexity:

O(n) - Each elimination takes O(1) time, and we perform n-1 eliminations.

Key Points:

Uses a circular linked list to model the problem
Each node points to the next person in the circle
Eliminates every second person by adjusting pointers
Continues until only one node remains (when node.next points to itself)