Reverse a Singly Linked List

Q: How do you reverse a singly linked list iteratively?

Walk through the list and point each node's next back to the previous node: It runs in O(n) time and O(1) space.

Q: How do you reverse a singly linked list recursively?

It also takes O(n) time, but it uses O(n) stack space. Java example: static Node reverse(Node head) { if (head == null || head.next == null) { return head; // empty list or last node } Node newHead = reverse(head.next); head.next.next = head; // the next node now points back to this one head.next = null; return newHead; }

Q: Why do you need three pointers in the iterative solution?

When you set current.next = previous, you lose the link to the rest of the list. The next pointer saves that link first, previous holds the already reversed part, and current is the node being reversed.

Q: What are the edge cases when reversing a linked list?

An empty list ( head == null ) should return null. A list with one node should return that node. The caller must use the returned value as the new head, as in head = reverse(head);.

Q: Write a Java method to reverse the first k nodes of a linked list.

For 1→2→3→4→5 with k = 3 the result is 3→2→1→4→5. Java example: static Node reverseFirstK(Node head, int k) { Node previous = null; Node current = head; int count = 0; while (current != null && count < k) { Node next = current.next; current.next = previous; previous = current; current = next; count++; } if (head != null) { head.next = current; // old head is now the k-th node; connect it to the rest } return previous; }

Q: How do you reverse a linked list in groups of k?

For 1→2→3→4→5→6 with k = 2 the result is 2→1→4→3→6→5. Java example: static Node reverseInGroups(Node head, int k) { Node previous = null; Node current = head; int count = 0; while (current != null && count < k) { Node next = current.next; current.next = previous; previous = current; current = next; count++; } if (current != null) { head.next = reverseInGroups(current, k); // old head is now the group's tail } return previous; }

Reverse a Singly Linked List

In this Linked List tutorial, we will see all about the reverse a linked list.

Example: If list contains 5 nodes

Input: 10 -> 20 -> 30 -> 40 -> 50
Output: 50 -> 40 -> 30 -> 20 -> 10

To reverse a linked list, there are two approaches:

Iterative Approach
Recursive Approach

Reverse a linked list using Iterative approach

Node.java

public class Node {
  int data;
  Node next;

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

ReverseUsingIterativeApproachInSLL.java

// Java program to reverse a linked list using Iterative approach
public class ReverseUsingIterativeApproachInSLL {

  static Node reverseList(Node head) {

    // Initialize three pointers: currNode, prevNode and nextNode
    Node currNode = head, prevNode = null, nextNode;

    while (currNode != null) {

      nextNode = currNode.next;
      currNode.next = prevNode;

      // Move pointers one position ahead
      prevNode = currNode;
      currNode = nextNode;
    }

    // Return the head of reversed linked list
    return prevNode;
  }

  // Method to print a linked list
  static void printList(Node node) {
    while (node != null) {
      System.out.print(" " + node.data);
      node = node.next;
    }
  }

  public static void main(String[] args) {
    // Create a linked list
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

    // Linked list will be created like this
    // 10 -> 20 -> 30 -> 40 -> 50

    System.out.print("Original Linked list:");
    printList(head);

    head = reverseList(head);

    System.out.print("\nReversed Linked List:");
    printList(head);
  }
}

Output

Original Linked list: 10 20 30 40 50

Reversed Linked List: 50 40 30 20 10

Reverse a linked list using Recursive approach

ReverseUsingRecursiveApproachInSLL.java

// Java program to reverse a linked list using Recursive approach
public class ReverseUsingRecursiveApproachInSLL {

  static Node reverseList(Node head) {

    // If we reached the last node means list is empty,
    // simply return the head of list
    if (head == null || head.next == null)
      return head;

    // reverse the rest of linked list and put the first
    // element at the end
    Node rest = reverseList(head.next);

    // Make the current head as last node of remaining
    // linked list
    head.next.next = head;

    head.next = null;

    return rest;
  }

  // Print a linked list
  static void printList(Node node) {
    while (node != null) {
      System.out.print(" " + node.data);
      node = node.next;
    }
  }

  public static void main(String[] args) {
    // Create a linked list
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

    // Linked list will be created like this
    // 10 -> 20 -> 30 -> 40 -> 50

    System.out.print("Original Linked list:");
    printList(head);

    head = reverseList(head);

    System.out.print("\nReversed Linked List:");
    printList(head);
  }
}

Output

Original Linked list: 10 20 30 40 50

Reversed Linked List: 50 40 30 20 10

Frequently Asked Questions (FAQ)

Q1. How do you reverse a singly linked list iteratively?

Walk through the list and point each node's next back to the previous node:

ReverseIterative.java

static Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    while (current != null) {
        Node next = current.next;   // save the rest of the list
        current.next = previous;    // reverse the link
        previous = current;         // move both pointers forward
        current = next;
    }
    return previous;                // new head
}

It runs in O(n) time and O(1) space.

Q2. How do you reverse a singly linked list recursively?

ReverseRecursive.java

static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;                // empty list or last node
    }
    Node newHead = reverse(head.next);
    head.next.next = head;          // the next node now points back to this one
    head.next = null;
    return newHead;
}

It also takes O(n) time, but it uses O(n) stack space.

Q3. Why do you need three pointers in the iterative solution?

When you set current.next = previous, you lose the link to the rest of the list. The next pointer saves that link first, previous holds the already reversed part, and current is the node being reversed.

Q4. What are the edge cases when reversing a linked list?

An empty list (head == null) should return null.
A list with one node should return that node.
The caller must use the returned value as the new head, as in head = reverse(head);.

Q5. Write a Java method to reverse the first k nodes of a linked list.

ReverseFirstK.java

static Node reverseFirstK(Node head, int k) {
    Node previous = null;
    Node current = head;
    int count = 0;
    while (current != null && count < k) {
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
        count++;
    }
    if (head != null) {
        head.next = current;        // old head is now the k-th node; connect it to the rest
    }
    return previous;
}

For 1→2→3→4→5 with k = 3 the result is 3→2→1→4→5.

Q6. How do you check whether a linked list is a palindrome?

Find the middle, reverse the second half, then compare both halves:

PalindromeList.java

static boolean isPalindrome(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    Node second = reverse(slow);          // reverse the second half
    Node first = head;
    while (second != null) {
        if (first.data != second.data) {
            return false;
        }
        first = first.next;
        second = second.next;
    }
    return true;
}

static Node reverse(Node head) {
    Node previous = null;
    while (head != null) {
        Node next = head.next;
        head.next = previous;
        previous = head;
        head = next;
    }
    return previous;
}

This takes O(n) time and O(1) space. Reverse the second half again afterwards if the list must stay unchanged.

Q7. Can you reverse a linked list using a stack?

Yes. Push every node onto a stack, then pop them and relink them in that order. It is easy to understand, but it needs O(n) extra space, so the pointer-reversal method is preferred.

Q8. Which is better for reversing in Java, iteration or recursion?

Iteration. Both are O(n) time, but recursion uses one stack frame per node, so a long list can throw a StackOverflowError. The recursive version is still a common interview question to test your understanding of recursion.

Q9. Does reversing a linked list create new nodes?

No. The standard algorithm reuses the same nodes and only changes their next references, which is why it needs only O(1) extra space.

Q10. How do you reverse a linked list in groups of k?

ReverseInGroups.java

static Node reverseInGroups(Node head, int k) {
    Node previous = null;
    Node current = head;
    int count = 0;
    while (current != null && count < k) {
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
        count++;
    }
    if (current != null) {
        head.next = reverseInGroups(current, k);   // old head is now the group's tail
    }
    return previous;
}

For 1→2→3→4→5→6 with k = 2 the result is 2→1→4→3→6→5.

Was this tutorial helpful?

Help Us Improve

Reverse a Singly Linked List

Reverse a linked list using Iterative approach

Reverse a linked list using Recursive approach

Frequently Asked Questions (FAQ)