1. 題目

給定一個單鏈表 L：L0→L1→…→Ln-1→Ln ，
將其重新排列后變?yōu)?#xff1a; L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。

示例 1: 給定鏈表 1->2->3->4, 重新排列為 1->4->2->3. 示例 2: 給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reorder-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 快慢指針找到中點，斷開，將后半部分反轉(zhuǎn)
• 合并兩條鏈表

class Solution { public:void reorderList(ListNode* head) {if(!head || !head->next || !head->next->next)return;ListNode *fast = head, *slow = head, *cur = head, *h, *nt;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}h = slow->next;//后半條鏈表slow->next = NULL;//斷開前后h = revList(h);//反轉(zhuǎn)后面的半條鏈表while(h)//依次合并{nt = cur->next;//第一條的下一個cur->next = h;//連接第二條的第1個h = h->next;//準備第二條的下一個cur->next->next = nt;//第二條的第一個接到第一條上cur = nt;}}ListNode* revList(ListNode* head)//反轉(zhuǎn)鏈表{if(!head || !head->next)return head;ListNode *prev=NULL, *cur=head, *nt = head->next;while(cur){cur->next = prev;prev = cur;cur = nt;if(nt)nt = nt->next;}return prev;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 143. 重排链表（链表反转+快慢指针）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。