206.Reverse Linked List

Posted on | In

Solution 1: accepted 1ms

Create a new node, looks not good. 

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode newHead = null;
    while (cur != null) {
        ListNode temp = new ListNode(cur.val);
        temp.next = newHead;
        newHead = temp;
        cur = cur.next;
    }
    return newHead;
}

Solution 2: accepted 0ms

No new nodes created yet still complicated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        if (newHead != null) {  // unnecessary condition
            head.next = newHead;
            newHead = head;
        } else {
            newHead = head;
            newHead.next = null;
        }
        head = next;
    }
    return newHead;
}

Solution 3: accepted 0ms

Should be the most concise iterative solution.

Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

Solution 4: accepted 1ms

Recursive solution.

  1. Base case: when head == null || head.next == null, we have the newHead, which is the last element in LinkedList.
  2. Recursive rule: next.next = current; current.next = null.

Time: O(n)
Space: O(n) (stack space consumption) 

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head; // find the newHead which remains throughout the program
    }
    ListNode newHead = reverseList(head.next);
    head.next.next = head; // if we use newHead.next, we lost nodes in the middle
    head.next = null;
    return newHead;       
}