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