题目讲解
143. 重排链表
文章来源:https://www.toymoban.com/news/detail-860770.html
算法讲解
1.使用快慢指针将链表分成两部分 2.将后半部分的链表逆置 3.使用双指针将连个链表分别连接结点在一起文章来源地址https://www.toymoban.com/news/detail-860770.html
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
//找到链表的中间节点 逆置后半部分链表
if(head == nullptr || head->next == nullptr || head->next->next == nullptr)return;
ListNode* slow = head;
ListNode* fast = slow->next;
//寻找中间节点
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
//走到这里slow指向的是中间节点的前一个结点 fast指向的是后半部分链表的最后一个节点
//逆置后半部分链表
ListNode* newhead = new ListNode(-1);
ListNode* cur = slow->next;
slow->next = nullptr; //断开两个部分的链表
//这一种头插法比较实用
while(cur)
{
ListNode* NextNode = cur->next;
cur->next = newhead->next;
newhead->next = cur;
cur = NextNode;
}
//合并链表
ListNode* retHead = new ListNode(-1);
ListNode* cur2 = head;
cur = newhead->next;
ListNode* phead = retHead;
while(cur2)
{
phead->next = cur2;
cur2 = cur2->next;
phead = phead->next;
if(cur)
{
phead->next = cur;
cur = cur->next;
phead = phead->next;
}
}
delete retHead;
delete newhead;
}
};
到了这里,关于【链表】Leetcode 重排链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!