Reverse a linked list

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Iterative reversal: use three pointers (prev, curr, next). Redirect each node's next pointer to its predecessor.

Algorithm

1prev=null, curr=head.
2While curr != null: next=curr.next. curr.next=prev. prev=curr. curr=next.
3Return prev (new head).

Example Walkthrough

Input: 1â†’2â†’3â†’4â†’5

1.nullâ†1 2â†’3â†’4â†’5. nullâ†1â†2 3â†’4â†’5. ... nullâ†1â†2â†3â†4â†5. prev=5.

Output: 5â†’4â†’3â†’2â†’1

Common Pitfalls

•Save curr.next BEFORE redirecting curr.next=prev, or you lose the rest of the list.

Reverse a linked list.java

Java

// Approach: Iterative three-pointer reversal: prev, current, next. Update links and advance.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

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

class Solution {
    Node reverseList(Node head) {
        Node prev = null;
        Node curr = head;

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

        return prev;
    }
}

Was this solution helpful?