江湖一笑浪滔滔，红尘尽忘了
题目
思路
链表这部分的题，不少都离不开单链表的反转，参考：反转一个单链表
这道题加上哨兵位的话会简单很多，如果不加的话，还需要分情况一下，像是从头节点开始反转还是头节点以后开始反转，有了哨兵位后就只有一种情况了。
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; }
