DSA From Zero to Job-ReadyLesson 7 of 28

Lessons

1 · Foundations (Think Like a Programmer)

2 · Data Structures and Recursion

3 · Core Algorithms and Reusable Patterns

4 · Advanced Interview Topics

5 · From Practice to Job-Ready

Lesson 7 of 28

Lesson 7 · Data Structures and Recursion

Linked Lists: Nodes, Pointers, and Pointer Reasoning

Build singly and doubly linked lists from scratch in Java, learn to reason about pointer changes step by step, and solve reversal, middle-finding, merging and cycle detection with clear diagrams and dry runs.

By Karthikeyan A20 min readTechnology

For

Learners who know arrays and want to understand pointer-based structures, which many interview questions rely on.

Level

Beginner

Before you start

Articles 3 to 6, especially Java references and classes, and arrays. You should know what null means.

On this page

Key takeaways

A linked list stores each value in a node that points to the next node. It gives O(1) insertion and deletion once you hold the right node, but O(n) access by position.
Most linked list bugs come from changing pointers in the wrong order. Save what you will need before you overwrite it.
A dummy node in front of the head removes special cases for empty lists and for changes at the head.
Reversal, finding the middle and detecting a cycle are all done with one or two pointers in O(n) time and O(1) space.
Arrays are simpler and usually faster in real programs. Choose a linked list when the problem really needs constant-time splicing.

A treasure hunt is a nice picture for a linked list. You start with one clue. It does not tell you where the treasure is. It tells you where to find the next clue. You follow the chain, one clue at a time, until a clue says "the end".

Nothing about the clues has to be stored in order. They can be in the garden, the kitchen and the attic. The only thing connecting them is "each one knows where the next is". That is a linked list, and it is the first data structure in this course that is not laid out side by side in memory.

Linked lists are a favourite in interviews, not because you will write them often at work, but because they make you reason about pointers (in Java, references). If you can keep a clear picture of what points to what, you can handle trees and graphs later.

What you will learn

What a node is, and how nodes form a singly linked list.
How to insert, delete and traverse, with clear pointer diagrams.
The dummy-node trick that removes edge cases.
How to reverse a list, find its middle and merge two sorted lists.
How to detect a cycle with two pointers, and why it works.
How a doubly linked list differs, and when to prefer an array.

Nodes and pointers

A node holds a value and a reference to the next node. We call the reference a pointer because it points to another object. The last node's next is null, meaning "there is nothing after me".

Java

static class Node {    int val;    Node next;    Node(int val) {        this.val = val;    }}

A list is described by its head: a reference to the first node. If you know the head, you can reach everything by following next. If you lose the head, the list is gone, so be careful never to overwrite it by accident.

Code

head | v[10|*]--->[20|*]--->[30|*]--->null

Each box is a node: the value, then the next pointer drawn as an arrow. An empty list is just head == null.

Traversal

The standard loop for walking a list is:

Java

for (Node cur = head; cur != null; cur = cur.next) {    // use cur.val}

cur starts at the head and moves forward. The loop ends when cur falls off the end and becomes null. Traversal visits n nodes, so it takes O(n) time. Note the condition cur != null: if you wrote cur.next != null you would stop one node early and, on an empty list, crash with NullPointerException.

Arrays versus linked lists

Operation	Array	Singly linked list
Access element number `i`	O(1)	O(n), you must walk `i` steps
Insert at the front	O(n), everything shifts	O(1)
Insert after a node you already hold	O(n)	O(1)
Delete a node you already hold (singly linked, with the previous node)	O(n)	O(1)
Search for a value	O(n)	O(n)
Memory per element	just the value	the value plus a reference, plus object overhead
Cache friendliness	Excellent, elements sit together	Poor, nodes can be scattered in memory

The fast insertion and deletion only apply once you are standing at the right place. Finding that place in a linked list costs O(n). So "linked lists are good at insertion" is only half true. Also, modern computers read memory in chunks, so scanning an array is much faster in practice than chasing pointers.

That is why, in everyday Java, you reach for ArrayList for sequences and ArrayDeque for queues. Java's LinkedList class exists but is rarely the best choice. Linked lists matter in interviews, and in places that really need constant-time splicing, such as some caches and the internals of other structures.

A singly linked list class

Let us build one. We keep only head and a size counter.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static class SinglyLinkedList {        private Node head;        private int size;        void addFirst(int value) {            Node node = new Node(value);            node.next = head;          // 1. the new node points at the old first node            head = node;               // 2. the head now points at the new node            size++;        }        void addLast(int value) {            Node node = new Node(value);            if (head == null) {                head = node;            } else {                Node cur = head;                while (cur.next != null) {   // walk to the last node                    cur = cur.next;                }                cur.next = node;            }            size++;        }        // Inserts value right after the first node holding target. Returns false if target is absent.        boolean insertAfter(int target, int value) {            for (Node cur = head; cur != null; cur = cur.next) {                if (cur.val == target) {                    Node node = new Node(value);                    node.next = cur.next;      // 1. new node takes over the rest of the list                    cur.next = node;           // 2. then the current node points to the new node                    size++;                    return true;                }            }            return false;        }        // Removes the first node holding value. Returns false if the value is absent.        boolean remove(int value) {            if (head == null) {                return false;            }            if (head.val == value) {           // special case: the head itself                head = head.next;                size--;                return true;            }            Node prev = head;            while (prev.next != null && prev.next.val != value) {                prev = prev.next;            }            if (prev.next == null) {                return false;                  // reached the end without finding it            }            prev.next = prev.next.next;        // skip over the removed node            size--;            return true;        }        int size() {            return size;        }        @Override        public String toString() {            StringBuilder sb = new StringBuilder();            for (Node cur = head; cur != null; cur = cur.next) {                sb.append(cur.val).append(" -> ");            }            return sb.append("null").toString();        }    }    public static void main(String[] args) {        SinglyLinkedList list = new SinglyLinkedList();        list.addLast(20);        list.addLast(30);        list.addFirst(10);        System.out.println(list + " (size " + list.size() + ")");        list.insertAfter(20, 25);        System.out.println(list);        System.out.println(list.remove(10) + " " + list);        System.out.println(list.remove(30) + " " + list);        System.out.println(list.remove(99) + " " + list);        System.out.println(list.insertAfter(99, 1) + " " + list.size());    }}

Code

10 -> 20 -> 30 -> null (size 3)10 -> 20 -> 25 -> 30 -> nulltrue 20 -> 25 -> 30 -> nulltrue 20 -> 25 -> nullfalse 20 -> 25 -> nullfalse 2

Pointer reasoning: the order of assignments matters

Look at insertAfter. We insert a new node X after node A, where the list is A -> B.

Code

Before:   A ---> BStep 1:   X.next = A.next      X ---> B          (X now points at B; A still points at B)Step 2:   A.next = X           A ---> X ---> B   (done)

If you do the steps in the opposite order, A.next = X first, you lose your only reference to B (it was stored in A.next), so you cannot set X.next = B afterwards. The rule of thumb:

For deletion, prev.next = prev.next.next makes the previous node skip the removed node. The removed node is no longer reachable from the list, and Java's garbage collector will free it eventually.

The dummy node

Notice how remove needed a special case for the head, and addLast needed one for the empty list. A dummy node (also called a sentinel) is a fake node placed before the real head. The real list is dummy.next. Because every real node now has a predecessor, the head is not special anymore.

Java

Node dummy = new Node(0);       // value does not matterdummy.next = head;// ... operate on the list using dummy as the starting point ...return dummy.next;              // the (possibly new) head

You will use this in the exercises. It is one of the most useful tricks in linked list problems.

Reversing a list

Problem. Reverse a singly linked list: 1 -> 2 -> 3 -> null becomes 3 -> 2 -> 1 -> null.

The idea is to walk down the list and flip each node's pointer so it points backwards. You need three references:

prev: the node behind us (starts as null).
curr: the node we are fixing (starts at the head).
next: the node ahead of us, saved before we overwrite curr.next.

Code

for each node:    next = curr.next      // 1. remember what comes after    curr.next = prev      // 2. flip the pointer    prev = curr           // 3. move prev forward    curr = next           // 4. move curr forward

Dry run on 1 -> 2 -> 3 -> null:

Round	`prev`	`curr`	`next` saved	After flipping
start	null	1
1	null	1	2	`1 -> null`; then `prev = 1`, `curr = 2`
2	1	2	3	`2 -> 1 -> null`; then `prev = 2`, `curr = 3`
3	2	3	null	`3 -> 2 -> 1 -> null`; then `prev = 3`, `curr = null`
end	3	null		loop ends, return `prev`

When curr becomes null, prev points at the last node we processed, which is the new head. The time is O(n) and the extra space is O(1): three references.

Finding the middle: slow and fast pointers

Problem. Return the middle node. For 1 -> 2 -> 3 -> 4 -> 5 it is 3. For an even length such as 1 -> 2 -> 3 -> 4, we choose the second middle, 3.

You could count the length first and walk half of it, which takes two passes. A neater method uses two pointers: slow moves one step at a time and fast moves two. When fast reaches the end, slow is at the middle, because it has travelled half the distance.

The loop condition is fast != null && fast.next != null. Both parts are needed, because fast jumps two nodes and must be able to step twice without falling off.

Merging two sorted lists

Problem. Merge two sorted lists into one sorted list by relinking the existing nodes.

Use a dummy node and a tail pointer that marks the end of the result so far. At each step, attach the smaller of the two current nodes to tail, and move forward in that list. When one list runs out, attach the rest of the other.

The following program contains build, show, reverse, middle and mergeSorted:

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static Node build(int... values) {        Node dummy = new Node(0);        Node tail = dummy;        for (int v : values) {            tail.next = new Node(v);            tail = tail.next;        }        return dummy.next;    }    static String show(Node head) {        StringBuilder sb = new StringBuilder();        for (Node cur = head; cur != null; cur = cur.next) {            sb.append(cur.val).append(" -> ");        }        return sb.append("null").toString();    }    static Node reverse(Node head) {        Node prev = null;        Node curr = head;        while (curr != null) {            Node next = curr.next;   // save before overwriting            curr.next = prev;            prev = curr;            curr = next;        }        return prev;    }    static Node middle(Node head) {        Node slow = head;        Node fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;        }        return slow;    }    static Node mergeSorted(Node a, Node b) {        Node dummy = new Node(0);        Node tail = dummy;        while (a != null && b != null) {            if (a.val <= b.val) {                tail.next = a;                a = a.next;            } else {                tail.next = b;                b = b.next;            }            tail = tail.next;        }        tail.next = (a != null) ? a : b;   // attach whatever is left        return dummy.next;    }    public static void main(String[] args) {        System.out.println(show(reverse(build(1, 2, 3, 4))));        System.out.println(show(reverse(build(7))));        System.out.println(show(reverse(null)));        System.out.println(middle(build(1, 2, 3, 4, 5)).val);        System.out.println(middle(build(1, 2, 3, 4)).val);        System.out.println(middle(build(9)).val);        System.out.println(show(mergeSorted(build(1, 4, 7), build(2, 3, 9, 10))));        System.out.println(show(mergeSorted(null, build(5))));        System.out.println(show(mergeSorted(build(1, 1), build(1))));    }}

Code

4 -> 3 -> 2 -> 1 -> null7 -> nullnull3391 -> 2 -> 3 -> 4 -> 7 -> 9 -> 10 -> null5 -> null1 -> 1 -> 1 -> null

The merge runs in O(n + m) time. It reuses the existing nodes, so the extra space is O(1). (We did not create new nodes, only changed next pointers.) Using <= keeps the merge stable: when values are equal, the node from the first list goes first.

Cycle detection

A list can accidentally (or deliberately, in a puzzle) contain a cycle: some node's next points back to an earlier node. Then traversal never reaches null, and a naive loop runs forever.

Brute force. Remember every node you visit in a HashSet. If you visit a node twice, there is a cycle. That is O(n) time but O(n) space.

Floyd's tortoise and hare. Use slow (one step) and fast (two steps). If the list ends, fast reaches null and there is no cycle. If there is a cycle, both pointers eventually run around it, and fast catches up with slow.

Why must they meet? Once both are inside the cycle, look at the gap between them (measured along the cycle). Each step, fast moves two and slow moves one, so the gap shrinks by exactly one. A gap that shrinks by one each step must reach zero, and zero gap means they stand on the same node. They cannot jump over each other, because the gap goes down by one each time.

Take the list 1 -> 2 -> 3 -> 4 -> 5 where 5 points back to 3:

Step	`slow`	`fast`
start	1	1
1	2	3
2	3	5
3	4	4 (5 -> 3 -> 4)

At step 3 they are on the same node, so there is a cycle.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static boolean hasCycle(Node head) {        Node slow = head;        Node fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) {          // same node, compared by reference                return true;            }        }        return false;    }    public static void main(String[] args) {        Node[] nodes = new Node[5];        for (int i = 0; i < 5; i++) {            nodes[i] = new Node(i + 1);            if (i > 0) {                nodes[i - 1].next = nodes[i];            }        }        System.out.println(hasCycle(nodes[0]));      // 1 -> 2 -> 3 -> 4 -> 5 -> null        nodes[4].next = nodes[2];                    // 5 now points back to 3        System.out.println(hasCycle(nodes[0]));        System.out.println(hasCycle(null));        Node single = new Node(1);        System.out.println(hasCycle(single));        single.next = single;                        // a node pointing at itself        System.out.println(hasCycle(single));    }}

Code

falsetruefalsefalsetrue

Complexity: time O(n), because once slow enters the cycle fast closes the gap within one lap of the cycle. Extra space O(1). Notice that we compare nodes with ==, which is correct here: we want to know whether they are the same object, not whether they hold equal values.

Doubly linked lists

In a doubly linked list, each node has both a next and a prev pointer. You can walk in both directions, and you can delete a node in O(1) given only the node itself, because it knows its predecessor.

The price is one more pointer per node, and twice as many pointers to keep correct. A common technique is to use two dummy nodes, a head sentinel and a tail sentinel. Then every real node has a neighbour on both sides, and insertion and removal are the same code everywhere.

Java

// File: Main.javapublic class Main {    static class DNode {        int val;        DNode prev;        DNode next;        DNode(int val) {            this.val = val;        }    }    static class DoublyLinkedList {        private final DNode head = new DNode(0);   // sentinel before the first real node        private final DNode tail = new DNode(0);   // sentinel after the last real node        private int size;        DoublyLinkedList() {            head.next = tail;            tail.prev = head;        }        DNode addFirst(int value) {            return insertBefore(head.next, value);        }        DNode addLast(int value) {            return insertBefore(tail, value);        }        // Inserts a new node just before the given node.        private DNode insertBefore(DNode node, int value) {            DNode created = new DNode(value);            created.prev = node.prev;            created.next = node;            node.prev.next = created;            node.prev = created;            size++;            return created;        }        // Removes a node in O(1), knowing only the node.        void remove(DNode node) {            node.prev.next = node.next;            node.next.prev = node.prev;            size--;        }        String forward() {            StringBuilder sb = new StringBuilder();            for (DNode cur = head.next; cur != tail; cur = cur.next) {                sb.append(cur.val).append(' ');            }            return sb.toString().trim();        }        String backward() {            StringBuilder sb = new StringBuilder();            for (DNode cur = tail.prev; cur != head; cur = cur.prev) {                sb.append(cur.val).append(' ');            }            return sb.toString().trim();        }        int size() {            return size;        }    }    public static void main(String[] args) {        DoublyLinkedList list = new DoublyLinkedList();        list.addLast(2);        DNode three = list.addLast(3);        list.addFirst(1);        list.addLast(4);        System.out.println(list.forward() + " | " + list.backward() + " | size " + list.size());        list.remove(three);                 // O(1): we already hold the node        System.out.println(list.forward() + " | " + list.backward() + " | size " + list.size());    }}

Code

1 2 3 4 | 4 3 2 1 | size 41 2 4 | 4 2 1 | size 3

A real-world use is a cache that must move the most recently used item to the front in constant time. Browser history ("back" and "forward") is another natural fit. We touch on both ideas again in Hashing and Stacks and Queues.

Complexity summary

Task	Time	Extra space
Traverse, search	O(n)	O(1)
`addFirst`	O(1)	O(1)
`addLast` without a tail pointer	O(n)	O(1)
`addLast` with a tail pointer	O(1)	O(1)
Insert after a node you hold	O(1)	O(1)
Delete by value	O(n) to find, O(1) to unlink	O(1)
Reverse	O(n)	O(1)
Middle (slow and fast)	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)
Cycle detection (Floyd)	O(n)	O(1)
Cycle detection with a `HashSet`	O(n)	O(n)

A recursive reversal is also possible, but it uses O(n) space for the call stack. Prefer the iterative one unless asked otherwise.

Edge cases and common mistakes

Empty list (head == null). Every method must handle it without throwing NullPointerException.
One node. Reversal, deletion and middle-finding all have different behaviour here. Test it.
Deleting the head or the tail. The head has no predecessor, and deleting the tail must set the previous next to null. A dummy node fixes the head case.
Losing the rest of the list. Overwriting curr.next before saving it is the classic reversal bug.
cur.next.next without checking. If cur.next is null, this throws. Check first.
Infinite loops. A list with a cycle never ends. A loop that forgets to advance cur also never ends.
Comparing nodes by value when you mean identity. To ask "is it the same node?", use ==. To ask "do they hold the same value?", compare val.
Forgetting size. If you keep a size counter, every insertion and deletion must update it.
Using a linked list when an array is better. If you need random access, use an array or an ArrayList.

Exercises

Exercise 1

Trace

Run the reversal code on 5 -> 6 -> 7 -> null. Write prev, curr and next at the start of each round, and the list formed by the reversed nodes so far.

Exercise 2: Remove the n-th node from the end

Given the head of a list and an integer n (1 means the last node), remove the n-th node from the end and return the head. Do it in one pass. Assume n is at most the length of the list.

Exercise 3: Remove duplicates from a sorted list

A sorted linked list may contain repeated values. Remove the repeats so each value appears once: 1 -> 1 -> 2 -> 3 -> 3 -> 3 becomes 1 -> 2 -> 3.

Exercise 4: Debug

This reversal loses most of the list. Find the bug, say what it returns for 1 -> 2 -> 3, and fix it.

Java

static Node reverseBuggy(Node head) {    Node prev = null;    Node curr = head;    while (curr != null) {        curr.next = prev;        prev = curr;        curr = curr.next;    }    return prev;}

Exercise 5: Interview-style

Given a list that contains a cycle, return the node where the cycle begins, or null if there is no cycle. Use O(1) extra space, and explain why your method is correct.

Show solutionHide solution

Round	`prev`	`curr`	`next`	Reversed part after the round
1	null	5	6	`5 -> null`
2	5	6	7	`6 -> 5 -> null`
3	6	7	null	`7 -> 6 -> 5 -> null`

After round 3, curr becomes null, the loop ends and we return prev, the node 7. The list is 7 -> 6 -> 5 -> null. In each round we flip exactly one pointer.

Exercise 2

Show solutionHide solution

Use two pointers with a gap of n nodes between them. Start both at a dummy node in front of the head. Move fast ahead n steps. Then move both together until fast is at the last node. At that moment slow is just before the node to remove, because the gap between them is n. Unlink it with slow.next = slow.next.next.

The dummy node handles the case where the node to remove is the head itself: then slow stays at the dummy.

One pass means O(length) time and O(1) space.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static Node build(int... values) {        Node dummy = new Node(0);        Node tail = dummy;        for (int v : values) {            tail.next = new Node(v);            tail = tail.next;        }        return dummy.next;    }    static String show(Node head) {        StringBuilder sb = new StringBuilder();        for (Node cur = head; cur != null; cur = cur.next) {            sb.append(cur.val).append(" -> ");        }        return sb.append("null").toString();    }    static Node removeNthFromEnd(Node head, int n) {        Node dummy = new Node(0);        dummy.next = head;        Node fast = dummy;        Node slow = dummy;        for (int i = 0; i < n; i++) {            fast = fast.next;            if (fast == null) {                throw new IllegalArgumentException("n is larger than the list");            }        }        while (fast.next != null) {            fast = fast.next;            slow = slow.next;        }        slow.next = slow.next.next;        return dummy.next;    }    public static void main(String[] args) {        System.out.println(show(removeNthFromEnd(build(1, 2, 3, 4, 5), 2)));        System.out.println(show(removeNthFromEnd(build(1, 2, 3, 4, 5), 5)));        System.out.println(show(removeNthFromEnd(build(1, 2, 3, 4, 5), 1)));        System.out.println(show(removeNthFromEnd(build(9), 1)));    }}

Code

1 -> 2 -> 3 -> 5 -> null2 -> 3 -> 4 -> 5 -> null1 -> 2 -> 3 -> 4 -> nullnull

Exercise 3

Show solutionHide solution

Because the list is sorted, equal values are next to each other. Walk with cur. If cur.val == cur.next.val, skip the next node by setting cur.next = cur.next.next, and do not advance cur, because the new next might also be a duplicate. Otherwise, move cur forward. Time O(n), space O(1). The head never changes, so no dummy node is needed.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static Node build(int... values) {        Node dummy = new Node(0);        Node tail = dummy;        for (int v : values) {            tail.next = new Node(v);            tail = tail.next;        }        return dummy.next;    }    static String show(Node head) {        StringBuilder sb = new StringBuilder();        for (Node cur = head; cur != null; cur = cur.next) {            sb.append(cur.val).append(" -> ");        }        return sb.append("null").toString();    }    static Node dedupeSorted(Node head) {        Node cur = head;        while (cur != null && cur.next != null) {            if (cur.val == cur.next.val) {                cur.next = cur.next.next;   // skip the duplicate, stay on cur            } else {                cur = cur.next;            }        }        return head;    }    public static void main(String[] args) {        System.out.println(show(dedupeSorted(build(1, 1, 2, 3, 3, 3))));        System.out.println(show(dedupeSorted(build(5, 5, 5))));        System.out.println(show(dedupeSorted(build(1, 2, 3))));        System.out.println(show(dedupeSorted(null)));    }}

Code

1 -> 2 -> 3 -> null5 -> null1 -> 2 -> 3 -> nullnull

Exercise 4

Show solutionHide solution

The bug is the last line of the loop: curr = curr.next. By then, curr.next has already been overwritten with prev, so curr moves backwards (to prev's old value) instead of forwards. The pointer to the rest of the list was lost before it was used. The fix is to save next = curr.next at the top of the loop and move to next at the bottom.

For 1 -> 2 -> 3: first round, curr = 1. curr.next = prev makes 1 -> null. prev = 1. curr = curr.next is null. The loop ends and the method returns 1, so the result is 1 -> null, and nodes 2 and 3 have been lost.

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static Node build(int... values) {        Node dummy = new Node(0);        Node tail = dummy;        for (int v : values) {            tail.next = new Node(v);            tail = tail.next;        }        return dummy.next;    }    static String show(Node head) {        StringBuilder sb = new StringBuilder();        for (Node cur = head; cur != null; cur = cur.next) {            sb.append(cur.val).append(" -> ");        }        return sb.append("null").toString();    }    static Node reverseBuggy(Node head) {        Node prev = null;        Node curr = head;        while (curr != null) {            curr.next = prev;            prev = curr;            curr = curr.next;        }        return prev;    }    static Node reverseFixed(Node head) {        Node prev = null;        Node curr = head;        while (curr != null) {            Node next = curr.next;            curr.next = prev;            prev = curr;            curr = next;        }        return prev;    }    public static void main(String[] args) {        System.out.println(show(reverseBuggy(build(1, 2, 3))));        System.out.println(show(reverseFixed(build(1, 2, 3))));    }}

Code

1 -> null3 -> 2 -> 1 -> null

Exercise 5

Show solutionHide solution

Method. First run Floyd's algorithm to find a meeting point m inside the cycle. If fast reaches null, return null. Then put one pointer, ptr, back at the head. Move ptr and the pointer at the meeting point one step at a time. They meet exactly at the node where the cycle begins.

Why it works. Let a be the number of steps from the head to the cycle start, L the cycle length, and b the number of steps from the cycle start to the meeting point (going around the cycle). When they meet:

slow has moved a + b steps.
fast has moved twice as many, 2(a + b). It is also a + b plus some whole number k of extra laps, so 2(a + b) = (a + b) + kL.
Therefore a + b = kL, and so a = kL - b.

Now look at what kL - b means: starting at the meeting point and walking kL - b steps goes forward the rest of the way around to the cycle start (L - b steps) and then possibly some extra laps. So the pointer from the meeting point and the pointer from the head both reach the cycle start after a steps.

Time O(n), space O(1).

Java

// File: Main.javapublic class Main {    static class Node {        int val;        Node next;        Node(int val) {            this.val = val;        }    }    static Node cycleStart(Node head) {        Node slow = head;        Node fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) {                Node ptr = head;                while (ptr != slow) {                    ptr = ptr.next;                    slow = slow.next;                }                return ptr;            }        }        return null;    }    static Node[] chain(int n) {        Node[] nodes = new Node[n];        for (int i = 0; i < n; i++) {            nodes[i] = new Node(i + 1);            if (i > 0) {                nodes[i - 1].next = nodes[i];            }        }        return nodes;    }    static String describe(Node node) {        return node == null ? "none" : String.valueOf(node.val);    }    public static void main(String[] args) {        Node[] a = chain(6);        a[5].next = a[2];                      // 6 points back to 3        System.out.println(describe(cycleStart(a[0])));        Node[] b = chain(4);        System.out.println(describe(cycleStart(b[0])));        Node[] c = chain(3);        c[2].next = c[0];                      // the whole list is a cycle        System.out.println(describe(cycleStart(c[0])));        Node[] d = chain(1);        d[0].next = d[0];        System.out.println(describe(cycleStart(d[0])));    }}

Code

3none11

Where to go next

Next: Stacks and Queues are built on the same pointer ideas, and are one of the most useful structures in everyday coding.
Related: the slow and fast pointers here are an example of Two Pointers. Trees in Trees and Binary Search Trees are nodes with two next pointers.
Practice habit: draw boxes and arrows for every linked list problem before you write code, and redraw after each pointer change.

Connected lessons

References

Show all 6 →

Linked from 3 guides

Other pages in the library that point here.

Linked Lists: Nodes, Pointers, and Pointer Reasoning

For

Level

Before you start

Key takeaways

What you will learn

Nodes and pointers

Traversal

Arrays versus linked lists

A singly linked list class

Pointer reasoning: the order of assignments matters

The dummy node

Reversing a list

Finding the middle: slow and fast pointers

Merging two sorted lists

Cycle detection

Doubly linked lists

Complexity summary

Edge cases and common mistakes

Exercises

Trace

Exercise 2: Remove the n-th node from the end

Exercise 3: Remove duplicates from a sorted list

Exercise 4: Debug

Exercise 5: Interview-style

Where to go next

Connected lessons

Linked from 3 guides

Keep reading

How to Learn Data Structures and Algorithms Without Burning Out

The OA Landscape: Platforms, Formats, Proctoring and Rules

A LinkedIn Profile That Gets Recruiter Messages