思路

1、首先利用快慢指針，將鏈表分成兩段。
2、將slow指針對(duì)應(yīng)的后半段鏈表進(jìn)行反轉(zhuǎn)（反轉(zhuǎn)鏈表操作）
3、利用歸并排序的思想，合并兩個(gè)鏈表。（tips:利用dummy節(jié)點(diǎn)可以提高效率）

/** @lc app=leetcode.cn id=143 lang=cpp** [143] 重排鏈表*/// @lc code=start /*** 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://ListNode* reverseList(ListNode* second){if(second==nullptr||second->next==nullptr) return second;ListNode* pre=nullptr;ListNode* cur=second;while(cur!=nullptr){ListNode* temp=cur->next;cur->next=pre;pre=cur;cur=temp;}return pre;}ListNode* mergeList(ListNode* head,ListNode* second){if(head==nullptr) return second;if(second==nullptr) return head;ListNode* pre=new ListNode(0);ListNode* HEAD=pre;while(head&&second){pre->next=head;//串上一個(gè)節(jié)點(diǎn)head=head->next;//該節(jié)點(diǎn)所在鏈表向后移一個(gè)pre=pre->next;//pre跟進(jìn)pre->next=second;second=second->next;pre=pre->next;}if(head==nullptr) pre->next=second;if(second==nullptr) pre->next=head;return HEAD->next;}ListNode* reorderList(ListNode* head) {if(head==nullptr||head->next==nullptr) return head;//找到鏈表中間結(jié)點(diǎn)，方法是利用快慢指針ListNode* slow=head,*fast=head->next;while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;}ListNode* second=reverseList(slow->next);slow->next=nullptr;//要把鏈表切成2段mergeList(head,second);return head;} };

總結(jié)

以上是生活随笔為你收集整理的重排链表！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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