题目

力扣

思路一 存储

用线性表把链表里的节点存下来，再一个个改变指向。

代码一

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr) return;
        vector<ListNode*> v;
        ListNode *h=head;
        while(h){
            v.push_back(h);
            h=h->next;
        }
        int i=0,j=v.size()-1;
        while(i<j){
            v[i]->next=v[j];
            i++;
            if(i==j) break;
            v[j]->next=v[i];
            j--;
        }
        //注意一定要把尾指针的next域置nullptr
        v[i]->next=nullptr;
    }
};

思路二 寻找中间节点+链表逆序+合并链表

先找到链表中点，再把后半部分链表逆序，再合并两个链表。

代码二

/**
 * 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) return;
        ListNode* mid=middleNode(head);
        ListNode* l1=head;
        ListNode* l2=mid->next;
        mid->next = nullptr;
        l2=reverseList(l2);
        mergeList(l1,l2);
    }
    
    ListNode* middleNode(ListNode* head){
        ListNode *slow=head,*fast=head;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* head){
        ListNode *pre=nullptr,*cur=head;
        while(cur){
            ListNode *t=cur->next;
            cur->next=pre;
            pre=cur;
            cur=t;
        }
        return pre;
    }

    void mergeList(ListNode* h1,ListNode* h2){
        while(h1 && h2){
            ListNode *t1=h1->next,*t2=h2->next;
            h1->next=h2;
            h1=t1;
            h2->next=h1;
            h2=t2;
        }
    }
};

思路三 递归

不断递归，处理除头节点和尾节点外的链表，返回尾节点，使头节点指向尾节点，尾节点指向处理后的链表的头节点，也就是head->next。

代码三

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr || head->next==nullptr || head->next->next==nullptr)
            return;
        int len=0;
        ListNode *h=head;
        while(h){
            len++;
            h=h->next;
        }
        reorderListHelper(head,len);
    }
    //返回重排好的链表之后的尾结点
    ListNode* reorderListHelper(ListNode* head,int len){
        if(len==1){
            ListNode* node=head->next;
            head->next=nullptr;
            return node;
        }

        if(len==2){
            ListNode* node=head->next->next;
            head->next->next=nullptr;
            return node;
        }

        ListNode* tail=reorderListHelper(head->next,len-2);
        ListNode* subHead=head->next;
        head->next=tail;
        ListNode* res=tail->next;
        tail->next=subHead;
        return res;
    }
};