Reverse a singly linked list(單鏈表).
剛看了覃超的直播，有點晚了，今天寫個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;
}
這遞歸又把我繞暈了苞也。調試了一下勉強理解了：
My thought:
在if語句的return之前, head會指向最后一個結點(p->next == null了),所以p會指向最后一個節(jié)點；然后就返回到上一層遞歸粘秆，這時候head已經不是最后一個節(jié)點了如迟，而是倒數第二個節(jié)點。然后把p指向head翻擒。head.next=null氓涣，不然會產生環(huán)。再返回逆序后的首節(jié)點p陋气。至于為什么每次都返回p劳吠，想不清了，暫時就只要想因為我們最終就需要返回p巩趁。
覃超直播的筆記：
clarification:邊界條件痒玩，極端情況問清
possible solutions: 想明白，比較各種解法议慰，想出最優(yōu)的蠢古；菜b和牛b的區(qū)別
coding
test cases
遞歸不要想很多層，會把自己繞暈别凹；只要想一層草讶，要知道后面的事它會做好
問考官會不會null，會不會太長炉菲；開始coding永遠檢查是否是合法的
寫堕战，多寫
prefer遞歸
1.01^365次方 37倍
遞歸里很多if判斷可能是不需要的
時間復雜度，空間復雜度非常非常重要
