Write a Program to reverse the Linked List (Both Iterative and recursive)

The problem, simply

You get a linked list: a chain of boxes where every box holds a number and an arrow pointing to the next box. The last box points to nothing, which we call null.

Make the chain go the other way. The last box should become the first box, and every arrow should point backwards. Give back the new first box.

A story to remember it

Picture it

After we are done, the same boxes stay where they are. Only the arrows change direction:

Examples

Way 1: the simple way

Read every number into a stack, like stacking plates. Then take the plates off the top one by one and write the numbers back into the boxes from the start. The plate you put on last comes off first, so the numbers come back in reverse order.

1. Walk the chain and push each number onto a stack.
2. Walk the chain again from the head.
3. For each box, pop the top number off the stack and write it into the box.

import java.util.ArrayDeque;
import java.util.Deque;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            stack.push(cur.val);           // put every number on the stack
        }
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = stack.pop();         // the last number comes off first
        }
        return head;
    }
}

How long it takes: we walk the chain two times, so the work grows with the number of boxes, O(n). How much extra room it needs: a stack as tall as the chain, O(n). It works, but it copies every number and it changes the values instead of the arrows, which some interviewers do not allow.

Way 2: the clever way

Do what you did with the train. Keep three fingers on the chain:

• prev is the part you already turned around. At the start it is null.
• curr is the box you are fixing right now.
• next is where you hold on to the rest of the chain so it does not get lost.

For each box: save next, flip the arrow of curr to point at prev, then slide prev and curr one step forward. When curr falls off the end, prev is the new head.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;      // the part that is already turned around
        ListNode curr = head;      // the box we are fixing now
        while (curr != null) {
            ListNode next = curr.next;  // hold on to the rest of the chain
            curr.next = prev;           // flip the arrow
            prev = curr;                // slide prev forward
            curr = next;                // slide curr forward
        }
        return prev;               // prev is the new head
    }
}

How long it takes: we touch each box once, O(n). How much extra room it needs: just three fingers, no matter how long the chain is, O(1).

Another way: recursion

You can also ask a helper to turn around everything after the first box, then fix the first box yourself. The helper asks another helper, and so on, until a helper gets a chain of one box, which is already turned around.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head; // zero or one box
        ListNode newHead = reverseList(head.next);  // helper turns the tail around
        head.next.next = head;                      // the box after me points back to me
        head.next = null;                           // I am the end now
        return newHead;
    }
}

This also takes O(n) time, but every waiting helper sits on the call stack, so it needs O(n) extra room. A chain of a million boxes can overflow the stack.

Watch out for

• Returning head at the end. After the flip, head is the last box. Return prev.
• Forgetting the empty list and the one box list. The loop handles both if prev starts at null.
• In the recursive way, forgetting head.next = null leaves a loop between the first two boxes.

What interviewers ask next

• Reverse only the boxes from position m to n. Walk to box m - 1, reverse n - m + 1 boxes with the same three fingers, then stitch both ends back.
• Reverse in groups of k. Reverse one group, then let the group's old first box point to the result of the next group.
• Can you do it faster than O(n)? No. Every arrow must change, and there are n arrows.
• Check if a list is a palindrome. Reverse the second half, then compare it with the first half.

Remember this

Grown-up words: the boxes are nodes, the arrows are next pointers, the three fingers are the three pointer technique, and the helpers waiting on each other are the recursion call stack.