【leetcode每日一题】Reorder List

港控/mmm° 2022-08-04 14:38 186阅读 0赞

题目：

Given a singly linked list L: L0→L1→…→Ln\-1→Ln,  
reorder it to: L0→Ln→L1→Ln\-1→L2→Ln\-2→…

You must do this in-place without altering the nodes' values.

For example,  
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.

解析：先将链表的后半部分反序，得到一个新链表。再把两个链表合并即可。步骤如下：

1）声明两个指针，快指针和慢指针，得到链表中间节点。

2）对链表后半部分进行逆序。

3）合并两个链表。

代码如下：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverse(ListNode *head)
        {
            if(head==NULL||head->next==NULL)
                return head;
            ListNode *p1=head,*p2=head->next,*p3;
            while(p2!=NULL)
            {
                p3=p2->next;
                p2->next=p1;
                p1=p2;
                p2=p3;
            }
            head->next=NULL;
            return p1;
        }
        ListNode* findMiddle(ListNode *head)
        {
            if(head==NULL||head->next==NULL)
                return head;
            ListNode *fast=head,*slow=head,*temp;
            while(fast!=NULL&&fast->next!=NULL)
            {
                fast=fast->next->next;
                slow=slow->next;
            }
    		temp=slow->next;
    		slow->next=NULL;
            return temp;
        }
        void reorderList(ListNode *head) {
            if(head==NULL||head->next==NULL)
                return;
            ListNode *pre=head;
            ListNode *tail=findMiddle(head);
            ListNode *post=reverse(tail);
            ListNode *temp1,*temp2;
            while(pre!=NULL&&post!=NULL)
            {
                temp1=pre->next;
                temp2=post->next;
                pre->next=post;
                post->next=temp1;
                pre=temp1;
                post=temp2;
            }
        }
    };