leetcode 143. Reorder List 双指针

柔情只为你懂 2022-06-08 06:06 156阅读 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\}.

最好的方法是使用双指针来得到中间结点，然后使用栈和队列来做。

要是直接遍历然后使用反序列表来做，也可以，不过非常烦。

代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /*class ListNode 
    {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
    }*/
    
    public class Solution 
    {
        
        public void reorderList(ListNode head) 
        {
            if(head==null || head.next==null)
                return ;
    
            //使用快慢指针把链表分为两个
            ListNode slow=head;
            ListNode fast=head;
            while(fast.next!=null && fast.next.next!=null)
            {
                fast=fast.next.next;
                slow=slow.next;
            }
    
            ListNode head1=head , head2=slow.next;
            slow.next=null;
    
            Queue<ListNode> myQueue=new LinkedList<>();
            ListNode cur=head1;
            while(cur!=null)
            {
                myQueue.add(cur);
                cur=cur.next;
            }
            Stack<ListNode> myStack=new Stack<>();
            cur=head2;
            while(cur!=null)
            {
                myStack.add(cur);
                cur=cur.next;
            }
    
    
            ListNode fin=new ListNode(-1);
            cur=fin;
            while(myQueue.isEmpty()==false && myStack.isEmpty()==false)
            {
                cur.next=myQueue.poll();
                cur=cur.next;
                cur.next=myStack.pop();
                cur=cur.next;
            }
            while(myQueue.isEmpty()==false)
            {
                cur.next=myQueue.poll();
                cur=cur.next;
            }
            while(myStack.isEmpty()==false)
            {
                cur.next=myStack.pop();
                cur=cur.next;
            }
    
            //这是最后一步，一定要设置
            cur.next=null;
            head=fin.next;
        }
    
        public static void main(String[] args) {
    
            ListNode one=new ListNode(1);
            one.next=new ListNode(2);
    
            Solution solution=new Solution();
            solution.reorderList(one);
        }
    }

下面是C++的做法，就是使用双指针来解决这个问题

代码如下：

#include <iostream>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    /*
    struct ListNode 
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        void reorderList(ListNode* head) 
        {
            if (head == NULL || head->next == NULL)
                return;
    
            ListNode* fast = head;
            ListNode* slow = head;
            while (fast->next != NULL && fast->next->next != NULL)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
            ListNode* h1 = head;
            ListNode* h2 = slow->next;
            slow->next = NULL;
    
            queue<ListNode*> que;
            ListNode* i = h1;
            while (i != NULL)
            {
                que.push(i);
                i = i->next;
            }
    
            stack<ListNode*> skt;
            i = h2;
            while (i != NULL)
            {
                skt.push(i);
                i = i->next;
            }
    
            ListNode* fin = new ListNode(-1);
            i = fin;
            while (!que.empty() && !skt.empty())
            {
                i->next = que.front();
                que.pop();
                i = i->next;
                i->next = skt.top();
                skt.pop();
                i = i->next;
            }
    
            while (!que.empty())
            {
                i->next = que.front();
                que.pop();
                i = i->next;
            }
    
            while (!skt.empty())
            {
                i->next = skt.top();
                skt.pop();
                i = i->next;
            }
    
            i->next = NULL;
            head = fin->next;
        }
    };