全部
［抄题］：
Reverse a singly linked list.
［思维问题］：
以为要用dummy node
［一句话思路］：
直接全部转过来就行了，用dummy node反而多余
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- return curt错了，应该是pre
［二刷］：
- 箭头左边就在等号左边，箭头右边就在等号右边
- 反正就是个模板
［总结］：
完全转过来之后，最早的prev应该是null
［复杂度］：Time complexity: O(1) Space complexity: O(1)
［英文数据结构，为什么不用别的数据结构］：
［其他解法］：
［Follow Up］：
［题目变变变］：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curt = head; while(curt != null) {
ListNode temp = curt.next;
curt.next = prev;
prev = curt;
curt = temp;
}
return prev;
}
}
m~n
［抄题］：
［思维问题］：
［一句话思路］：
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
千万别画错了！
［一刷］：
- 第一层corner case是m,n的关系，head本身就为空
- 用已经有的head表示m-1，能少定义一个变量。不要一下全定义了，要用的时候再定义。
- 先定义nNode 就是 mNode，然后对nNode操作就够了
- 翻转m-n用for循环就行了
- 一定要判断是否为空再.next
- ListNode premNode = head;声明和指定可以统一
- dummy是第一个节点，应该把head指向它，从它开始找
- 理解四部翻转法每一步的含义：存2next，当前反指，往后移 这道题里面只有m，postn需要移动
- if (head == null || m >= n)时，无法删除，还是要返回head
5->null
1
1---------5［总结］：
链表的头尾衔接关系别画错了，不方便debug
［复杂度］：Time complexity: O(1) Space complexity: O(1)
［英文数据结构，为什么不用别的数据结构］：
linked list节约空间复杂度
［其他解法］：
［Follow Up］：
［题目变变变］：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || m >= n) {
return head;
} ListNode dummy = new ListNode(0);
dummy.next = head;
//search for m-1 th
head = dummy;
for(int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}
//reverse
ListNode premNode = head;
ListNode mNode = premNode.next;
ListNode nNode = mNode;
ListNode postnNode = nNode.next;
for (int i = m; i < n; i++) {
ListNode temp = postnNode.next;//2cun
postnNode.next = nNode;//hui
nNode = postnNode;//xia yi
postnNode = temp;
} //join up
mNode.next = postnNode;
premNode.next = nNode; return dummy.next;
}
}