LL 6 - Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list. (link)

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output:

Solution

Brute force Approach

We reverse the linked list by pushing all the elements into a stack. We then store the reversed order in the linked list by poping elements from the stack.

Time - O(n)

Space - O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        Stack<Integer> st = new Stack<>();

        ListNode temp = head;

        while(temp!=null){
            st.push(temp.val);
            temp = temp.next;
        }

        temp = head;
        while(temp!=null){
            temp.val = st.pop();
            temp = temp.next;
        }

        return head;
    }
}

Optimal Approach - Iterative

We stand on a Node and change the next pointer to point to the previous node. Before changing the next pointer we store the reference in one variable and do the modification. Later, we move to the same next node reference which was stored. Also, we store the previous node in prev pointer as it is required. In this way, we reverse a linked list.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp = head;
        ListNode prev = null;

        while(temp!=null){

            ListNode next = temp.next;

            temp.next = prev;
            prev = temp;

            temp = next;
        }

        return prev;
    }
}

Optimal Approach - Recursive

In the recursive approach, we instruct the function to reverse the linked list starting from the next node and return the head of the reversed linked list. Once we have the new head of the reversed list, we need to append the current head to the end of the reversed list. Adding the current head to the tail of the new list is straightforward because we know that the tail is current head's next. Therefore, we direct the tail to the current head and deisgnate the current head node as tail by pointing it to null. Finally, we return the new Head node .

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next==null) return head;

        ListNode newHead = reverseList(head.next);
        ListNode front = head.next;
        front.next = head;
        head.next = null;
        return newHead;
    }
}