无论是1，还是2，删除链表都需要3个节点，只是现在这种最新写法只把cur作为了判断循环的依据，并且下一个节点的生成放在循环内。
206. Reverse Linked List
之前在牛客上的写法：
错误代码:
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL)
return NULL;
ListNode* p1 = pHead;
ListNode* p2 = pHead->next;
ListNode* p3 = pHead->next->next;
pHead->next = NULL;
while(p3 != NULL){
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
return p2;
}
};
此代码会报“段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起”
如果链表只有一个节点，那p2就是空指针，p3就是空指针的下一个指针，但空指针是没有next的
正确代码:
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL)
return NULL;
else if(pHead->next == NULL)
return pHead;
ListNode* p1 = pHead;
ListNode* p2 = pHead->next;
ListNode* p3 = pHead->next->next;
pHead->next = NULL;
while(p3 != NULL){
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
return p2;
}
};
个人觉得这种以当前节点为循环判断条件的方式比较好：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
while(head){
ListNode* tmp = head->next;
head->next = pre;
pre = head;
head = tmp;
}
return pre;
}
};
92. Reverse Linked List II
依旧要在循环开始前获得pre和cur指针。
有个边界条件是m = 1的时候，可能第一个节点，即head指针也要反转，所以返回的时候返回head会出错。所以申请了一个指针，并且下一个节点就是head，这样无论哪种情况，都是申请指针的下一个节点。
注意pre的初始化也是在head之前，因为m <= 1实际上都是在head之前。还要注意m-1的设置，并且这个for循环就是找pre的位置。
i=m;i < n 比如3个节点的reverse，实际上只用操作2次就好了。
思路上：每次把cur的下一个节点旋转到cur之前去，pre节点实际上是不变的。
错误写法：
错误在tmp->next = cur; 第一次循环是对的，后面的就错了。cur指针是不变的，但是pre和cur之间的个数在增加，真正要放的位置是pre后面
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* pre = new ListNode(-),*res = pre;
pre->next = head;
res = pre;
for(int i = ;i < m - ;i++)
pre = pre->next;
ListNode* cur = pre->next;
for(int i = m;i < n;i++){
ListNode* tmp = cur->next;
cur->next = tmp->next;
tmp->next = cur;
pre->next = tmp;
}
return res->next;
}
};
正确写法：
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* pre = new ListNode(-),*res = pre;
pre->next = head;
res = pre;
for(int i = ;i < m - ;i++)
pre = pre->next;
ListNode* cur = pre->next;
for(int i = m;i < n;i++){
ListNode* tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
}
return res->next;
}
};