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会指向最后一个节点；然后就返回到上一层递归，这时候head已经不是最后一个节点了，而是倒数第二个节点。然后把p指向head。head.next=null，不然会产生环。再返回逆序后的首节点p。至于为什么每次都返回p，想不清了，暂时就只要想因为我们最终就需要返回p。
覃超直播的笔记：
clarification:边界条件，极端情况问清
possible solutions: 想明白，比较各种解法，想出最优的；菜b和牛b的区别
coding
test cases
递归不要想很多层，会把自己绕晕；只要想一层，要知道后面的事它会做好
问考官会不会null，会不会太长；开始coding永远检查是否是合法的
写，多写
prefer递归
1.01^365次方 37倍
递归里很多if判断可能是不需要的
时间复杂度，空间复杂度非常非常重要
