Day82 | 靈神 | 快慢指針 重排鏈表

143.重排鏈表

143. 重排鏈表 - 力扣（LeetCode）

思路：

筆者直接給跪了，這個難度真是mid嗎

直接去看靈神的視頻

環形鏈表II【基礎算法精講 07】_嗶哩嗶哩_bilibili

1.簡單來說就是，找到鏈表的中間節點，然后翻轉后半部分鏈表，然后一次修改指針就好

2.其實自己做的時候想的時候暴力去做，就是每次都找一下最后一個節點的前一個結點，然后修改指針，就是復雜度比較高

3.取逛了逛評論區，佬們還有一個思路我也覺得不錯，就直接雙端隊列將元素全部加進去，然后前面后面分別來一個，構成新的鏈表，這樣簡單無腦，筆者覺得這個思路也很好

靈神思路中可能的疑惑？

1.為啥要找中間節點？

我覺得是因為中間結點剛好是不需要放到前面去的最后一個節點，它之后的節點都得放到前面去，不管n是奇數還是偶數

2.為啥要反轉鏈表？

這樣可以更好的找到最后一個節點，即要放到前面的節點，不需要和暴力做法一樣每次都去遍歷一次

完整代碼：

class Solution {
public://876.鏈表的中間節點ListNode* middleNode(ListNode* head) {ListNode *l=head;ListNode *r=head;while(r!=nullptr&&r->next!=nullptr){l=l->next;r=r->next->next;}return l;}//206.反轉鏈表ListNode* reverseList(ListNode* head) {ListNode *p=head;ListNode *pre=nullptr;while(p!=nullptr){ListNode* q=p->next;p->next=pre;pre=p;p=q;}return pre;}void reorderList(ListNode* head) {ListNode *mid=middleNode(head);ListNode *head2=reverseList(mid);while(head2->next){ListNode* ntx1=head->next;ListNode *ntx2=head2->next;head->next=head2;head2->next=ntx1;head=ntx1;head2=ntx2;}}   
};