无论是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(-1),*res = pre; pre->next = head; res = pre; for(int i = 0;i < m - 1;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(-1),*res = pre; pre->next = head; res = pre; for(int i = 0;i < m - 1;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; } };