LeetCode 题解-206. Reverse Linked List

对Leetcode 206. Reverse Linked List 题目的求解。

Problem Description#

Reverse a singly linked list.

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

Example#

Example 1

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

Analysis#

这道题的核心其实是指针的交换。方便起见，我们引入多余的head指针，指向第一个node。迭代实现和递归实现如下。

Iterative Solution#

1
class Solution {
2
    ListNode zero = new ListNode(0);
3
    zero.next = head;
4
    ListNode tmp = new ListNode(0);
5
    while (head != null){
6
        tmp = head.next;
7
        if (tmp == null) break;
8
        head.next = head.next.next;
9
        tmp.next = zero.next;
10
        zero.next = tmp;
11
    }
12
    return zero.next;
13
}

Recursive Solution#

递归方法的核心是先reverse剩余的n-1个指针，再将第一个指针接到最后。

1
class Solution {
2
    public static ListNode reverseList(ListNode head) {
3
        if (head == null) return head;
4
        ListNode tail = head;
5
        while (tail.next != null){
6
            tail = tail.next;
7
        }
8
        myreverse(head, tail);
9
        head.next = null;
10
        return tail;
11
    }
12
    public static void myreverse(ListNode head, ListNode tail){
13
        if (head == tail){
14
            return ;
15
        }
16
        myreverse(head.next, tail);
17
        head.next.next = head;
18
    }
19
}