Solving Reverse Linked List

To see the question, click here.

Naive Approach

The idea is to iterate through the linked list and store the node values by adding them in an ArrayList . We reverse the ArrayList by using Collections class. We then iterate through the linked list again to swap the node values with the values of the ArrayList.

// TC: O(n)
// SC: O(n)

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }

        Collections.reverse(list);

        ListNode anotherTemp = head;
        for (int i = 0; i < list.size(); i++) {
            anotherTemp.val = list.get(i);
            anotherTemp = anotherTemp.next;
        }

        return head;
    }

    public static void main(String[] args) {
        ReverseLinkedList rl = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode res = rl.reverseList(head);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

Performance

The time complexity of the reverseList method is O(n). This is because we iterate through the linked list once to store the values in a list, then reverse the list, and finally iterate through the linked list again to update the values. The space complexity is also O(n) because we are storing all the values of the linked list nodes.

Refined Approach

The idea is to iterate through the linked list and store the node values by pushing them onto a Stack . We then iterate through the linked list again to swap the node values with the values that are being popped from the Stack.

// TC: O(n)
// SC: O(n)

import java.util.Stack;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }

        ListNode anotherTemp = head;
        while (anotherTemp != null) {
            anotherTemp.val = stack.pop();
            anotherTemp = anotherTemp.next;
        }

        return head;
    }

    public static void main(String[] args) {
        ReverseLinkedList rl = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode res = rl.reverseList(head);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

Performance

The time complexity of the reverseList method is O(n) because we iterate through the linked list twice - once to push the values onto the stack and once to pop the values from the stack and update the linked list nodes. The space complexity is also O(n) because we use a stack to store all the values of the linked list nodes.

Efficient Approach

Using the In-place reversal technique, we can reverse the linked list without additional data structures.

// TC: O(n)
// SC: O(1)

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head, next = null;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

    public static void main(String[] args) {
        ReverseLinkedList rl = new ReverseLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode res = rl.reverseList(head);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

Performance

The time complexity of the reverseList method is O(n) because we iterate through each node in the linked list once. The space complexity is O(1) because we use constant extra space regardless of the linked list size.

Thank you for reading!

Check out other DSA patterns here.

You can support me by buying me a book.