Star

LeetCode 206. Reverse Linked List

Posted on | In |

Quesstion

Reverse a singly linked list.

click to show more hints.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Explanation

Iterative Solution

定义一个previous node，一个current node，倒过来。并记下之前的后面一个节点，循环。

Recursive Solution

Code

Iterative Solution

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

Recursive Solution

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