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