Linked List Problems in Java: Reversal, Cycle Detection, and the Interview Classics Traced

Linked list problems are rarely difficult because of the big idea. They are difficult because one overwritten pointer can cut off the unprocessed part of the list. In Java, the safest habit is to state what each reference owns before every assignment, especially when reversing links in place or moving two pointers at different speeds.

The Java node and three pointer rules

A minimal singly linked list node stores a value and a reference to the next node:

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
    }
}

The final node points to null. That simple chain becomes easier to manipulate when you follow three rules.

1. Save curr.next before changing it. Otherwise, you can lose every node after curr.

2. Use a dummy head for insertion or deletion near the front. It makes the original head behave like any other node.

3. Check the boundaries. An empty list, a one-node list, and the tail all bring null into the logic.

These are not style preferences. They remove the most common failure modes from pointer code.

Iterative linked list reversal, fully traced

Reverse 1 -> 2 -> 3 -> 4 -> null with three references: prev, curr, and next. Before the loop, prev = null and curr = 1.

Node reverse(Node head) {
    Node prev = null;
    Node curr = head;

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

Now trace every assignment rather than trusting the code by sight.

• Step 1: save next = 2. Set 1.next = null. Move prev to 1 and curr to 2. The reversed part is 1 -> null.

• Step 2: save next = 3. Set 2.next = 1. Move prev to 2 and curr to 3. The reversed part is 2 -> 1 -> null.

• Step 3: save next = 4. Set 3.next = 2. Move prev to 3 and curr to 4. The reversed part is 3 -> 2 -> 1 -> null.

• Step 4: save next = null. Set 4.next = 3. Move prev to 4 and curr to null. The reversed part is 4 -> 3 -> 2 -> 1 -> null.

The loop stops because curr == null. At that moment, prev points to node 4, so it is the new head. Each node is visited once, giving O(n) time, and only three references are used, giving O(1) extra space.

The line to protect is Node next = curr.next. Move it below curr.next = prev, and the reference to the remaining list is gone.

Fast and slow pointers for the middle and a cycle

Two pointers can encode distance without a counter. For the middle node, move slow one edge at a time and fast two. When fast reaches null or the tail, slow is at the middle; with the guard fast != null && fast.next != null, an even-length list selects the second of its two middle nodes. The same guard keeps both even and odd lengths safe.

Floyd's cycle detection uses the same speeds on a list that may not end. Consider:

1 -> 2 -> 3 -> 4 -> 5, with node 5 pointing back to node 3.

The cycle is 3 -> 4 -> 5 -> 3. Start both pointers at node 1.

On iteration 3, fast travels 5 -> 3 -> 4. Both references now point to node 4, so a cycle exists.

To locate the entry, keep one pointer at the meeting node and reset the other to the head. Move both one edge per step:

• (1, 4) becomes (2, 5).

• (2, 5) becomes (3, 3).

They meet at node 3, which is the cycle entry. Detection takes O(n) time and O(1) extra space, without modifying the list.

The same trace becomes a Java method that returns the cycle entry rather than only a boolean:

Node findCycleEntry(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 fromHead = head;
            while (fromHead != slow) {
                fromHead = fromHead.next;
                slow = slow.next;
            }
            return fromHead;
        }
    }
    return null;
}

For the five-node example, slow and fast meet at node 4. From there, fromHead advances 1 -> 2 -> 3 while slow advances 4 -> 5 -> 3, so the method returns node 3. On an acyclic list, fast reaches null and the method returns null.

Other linked list classics and the trick behind each

Once reversal and two-speed movement are familiar, several interview questions become variations rather than new algorithms.

Merge two sorted lists

Create a dummy head and maintain a tail. Compare the first unmerged node from each list, attach the smaller one to tail, and advance that list. For 1 -> 4 and 2 -> 3 -> 5, the chosen tail values are 1 from the left, 2 from the right, 3 from the right, and 4 from the left; then append the remaining 5. The merged result is 1 -> 2 -> 3 -> 4 -> 5, and the dummy node avoids separate logic for choosing its first node.

Remove the nth node from the end

Start both references at a dummy head and advance the leader n + 1 edges before moving the leader and follower together. On dummy -> 1 -> 2 -> 3 -> 4 -> 5 with n = 2, the pair starts at (3, dummy) after those three lead moves, then becomes (4, 1), (5, 2), and (null, 3). The follower is now immediately before node 4, so follower.next = follower.next.next produces 1 -> 2 -> 3 -> 5. Counting n + 1 edges from the dummy removes the off-by-one ambiguity.

Check whether a list is a palindrome

Find the middle with fast and slow pointers, reverse the second half, and compare the two halves node by node. For 1 -> 2 -> 3 -> 2 -> 1, slow stops at 3; reversing the suffix changes 2 -> 1 into 1 -> 2, which matches the first two nodes. Equal pairs make the list a palindrome, and reversing the suffix again restores the caller's original list.

The DSA Interview Questions for Placements: The Patterns Freshers Must Know guide shows how this pattern sits beside arrays, stacks, trees, and graphs.

Traps to catch before you submit

• Rewiring curr.next before saving next loses the remaining chain.

• Dereferencing the head without checking it breaks on an empty list.

• Omitting a dummy head creates fragile special cases for front insertion and deletion.

• Using fast.next.next without both null checks breaks at the tail.

• Treating the nth-from-end gap casually creates an off-by-one error.

• Returning head after reversal returns the old head, now the tail. Return prev.

For coding rounds, the expected target for these core operations is usually linear time and constant auxiliary space. Practise that implementation standard in the DSA using Java course, then mix the patterns with broader Coding & Skills problems.

The short version and your next step

Save next before rewiring, use a dummy head when the front can change, and keep the fast-slow pattern ready. The two traces to remember are 1 -> 2 -> 3 -> 4 becoming 4 -> 3 -> 2 -> 1, and the cycle pointers meeting at 4 before locating entry 3.

The Data Structure practice bank offers over 1,500 questions, including over 140 on linked lists. Work through those traces alongside the Mera Placement Hoga bundle, and write the pointer positions on paper whenever an answer surprises you.