反转链表II

---

江湖一笑浪滔滔，红尘尽忘了

---

题目

示例

 

---

---

       思路 

链表这部分的题，不少都离不开单链表的反转，参考：反转一个单链表

这道题加上哨兵位的话会简单很多，如果不加的话，还需要分情况一下，像是从头节点开始反转还是头节点以后开始反转，有了哨兵位后就只有一种情况了。

malloc一个哨兵位，next指向head，遍历两次，一次找起点，，开始节点的前一个节点保存下来，为了连接reverse返回的节点地址；一次找结束，结束的节点next节点保存下来，并使该节点的next指针置空，剩下的就是连接的问题，比较简单。

 

---

---

代码 

struct ListNode* reverse(struct ListNode* head)
{struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = NULL;if(n2)n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{if(head == NULL || left >= right){return head;}struct ListNode* phead = malloc(sizeof(struct ListNode));phead->next = head;struct ListNode* prev = NULL;struct ListNode* cur1 = phead;struct ListNode* cur2 = phead;struct ListNode* Back = NULL;struct ListNode* next = NULL;int num1 = left;int num2 = right;while(num1--){prev = cur1;cur1 = cur1->next;}while(num2--){cur2 = cur2->next;}next = cur2->next;cur2->next = NULL;Back = reverse(cur1);prev->next = Back;int num = right - left;while(num--){Back = Back->next;}if(Back)Back->next = next;head = phead->next;free(phead);return head;
}

---

---

 

个人主页：Lei宝啊 

愿所有美好如期而遇