L206 Reverse LinkedList

Problem:

Reverse a singly linked list.

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Solution:

S1 : Iteration

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 first. 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;
}

S2: Recursion

We need to create a new head as the head of the reversed linked list. head.next.next is change the direction of the pointer.

head.next must be null, if not , there is a cycle in the linked list.

• TC : O(n), n is the length of the list

• SC: O(n), The extra space comes from implicit stack space due to recursion. The recursion could go up to n levels deep.

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