Leetcode 206 - Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/
https://leetcode.com/articles/reverse-linked-list/

Assume that we have linked list 1 → 2 → 3 → Ø, we would like to change it to Ø ← 1 ← 2 ← 3.

While you are traversing the list, change the current node's next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

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

http://www.jiuzhang.com/solutions/reverse-linked-list/

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

Reversing linked list iteratively and recursively -- LeetCode

1) The iterative way:

1 2 3 4 5 6 7 8 9 10 11 12

void reverse(Node*& head) {   if (!head) return;   Node* prev = NULL;   Node* curr = head;   while (curr) {     Node* next = curr->next;     curr->next = prev;     prev = curr;     curr = next;   }   head = prev; }

Please do note that the head pointer is passed in by reference. If you have trouble understanding the syntax, think the pointer as a type, and an & sign followed by a type signifies the variable is passed by reference. The head pointer must be passed in by reference whenever there might be a change to the head pointer itself!

2) The recursive way:

Approach #2 (Recursive)

The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let's assume the list is: n1 → … → nk-1 → nk → nk+1 → … → nm → Ø

Assume from node nk+1 to nm had been reversed and you are at node nk.

n1 → … → nk-1 → nk → nk+1 ← … ← nm

We want nk+1’s next node to point to nk.

So,

nk.next.next = nk;

Be very careful that n₁'s next must point to Ø. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

• Time complexity : $O(n)$. Assume that $n$ is the list's length, the time complexity is $O(n)$.
• Space complexity : $O(n)$. The extra space comes from implicit stack space due to recursion. The recursion could go up to $n$ levels deep

1 2 3 4 5 6 7 8 9

void reverse(Node*& p) {   if (!p) return;   Node* rest = p->next;   if (!rest) return;   reverse(rest);   p->next->next = p;   p->next = NULL;   p = rest; }

EPI Java Code

Reverse a singly linked list

ReverseLinkedListRecursiveTemplate.java
  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node<T> newHead = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }
ReverseLinkedListIterativeTemplate.java
  public static <T> Node<T> reverseLinkedList(Node<T> head) {
    Node<T> prev = null, curr = head;
    while (curr != null) {
      Node<T> temp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = temp;
    }
    return prev;
  }