Reverse a singly linked list(單鏈表).

剛看了覃超的直播，有點(diǎn)晚了，今天寫個(gè)easy題睡覺。

下面的題解引用editorial的。

Approach #1 (Iterative) [Accepted]

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) {
        if (head == null) return null;
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

Approach #2 (Recursive) [Accepted]

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 n1'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;
}

這遞歸又把我繞暈了。調(diào)試了一下勉強(qiáng)理解了：

My thought:

在if語句的return之前, head會(huì)指向最后一個(gè)結(jié)點(diǎn)(p->next == null了),所以p會(huì)指向最后一個(gè)節(jié)點(diǎn)；然后就返回到上一層遞歸，這時(shí)候head已經(jīng)不是最后一個(gè)節(jié)點(diǎn)了，而是倒數(shù)第二個(gè)節(jié)點(diǎn)。然后把p指向head。head.next=null，不然會(huì)產(chǎn)生環(huán)。再返回逆序后的首節(jié)點(diǎn)p。至于為什么每次都返回p，想不清了，暫時(shí)就只要想因?yàn)槲覀冏罱K就需要返回p。

覃超直播的筆記：

clarification:邊界條件，極端情況問清
possible solutions: 想明白，比較各種解法，想出最優(yōu)的；菜b和牛b的區(qū)別
coding
test cases

遞歸不要想很多層，會(huì)把自己繞暈；只要想一層，要知道后面的事它會(huì)做好

問考官會(huì)不會(huì)null，會(huì)不會(huì)太長(zhǎng)；開始coding永遠(yuǎn)檢查是否是合法的

寫，多寫

prefer遞歸

1.01^365次方 37倍

遞歸里很多if判斷可能是不需要的
時(shí)間復(fù)雜度，空間復(fù)雜度非常非常重要