重新排列链表

左手的ㄟ右手 2022-08-26 12:19 179阅读 0赞

**LeetCode :**

### Reorder List ###

LeetCode上有下面这样一个题目，比较有意思，拿来实现，权当练习基本功了：

### Reorder List ###

Total Accepted: 8598 Total Submissions: 44508 [My Submissions][]

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}`.

题目要求我们算法是in-place的，因此我们不能够通过交换value的值来实现，只能对链表进行重新链接。

对于本题，我的思路是这样的：经过观察发现，reorder后的链表是原来链表 **前半部分**与 **后半部分的逆序**交叉链接得到的。

因此：

1. 首先找到原来链表的中间节点mid，将原链表分成两部分；

2. 前面部分存入一个队列queue中；

3. 后半部分则存入一个栈stack中（这样取出来的时候自动逆序）；

4. 然后再将队列这栈中的元素交替取出，并链接取来，从而得到reorder后的结果。

思想很简单，下面直接上已经AC过的代码，如果你还有更好的思路请告诉我，希望学习进步：

#include <iostream>
    #include <fstream>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <algorithm>
    using namespace std;
    
     struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
     };
    
    class Solution {
    public:
    	//找到链表的中间节点
    	ListNode *findMiddle(ListNode *head) 
    	{
    		if (head == NULL) return NULL ;
    		ListNode *p1 = head ;
    		ListNode *p2 = head->next ;
    
    		while(p2 != NULL && p2->next != NULL)
    		{
    			p1 = p1->next ;
    			p2 = p2->next->next ;
    		}
    		return p1 ;
    	}
    
        void reorderList(ListNode *head) {
    
            if (head == NULL) return ;
    		if (head->next == NULL) return ;
    
    		ListNode *tmpHead = head ;
    		queue<ListNode*> q ; //使用队列存储前半部分
    		stack<ListNode*> s ;  //使用栈保存后半部分
    
    		ListNode *midPtr = findMiddle(head) ;
    		midPtr = midPtr->next ;
    		//前半部分存入队列
    		while (tmpHead != midPtr)
    		{
    			q.push(tmpHead) ;
    			tmpHead = tmpHead->next ;
    		}
    		//后半部分存入栈
    		while (midPtr != NULL)
    		{
    			s.push(midPtr) ;
    			midPtr = midPtr->next ;
    		}
    
    		//将两部分合并
    		ListNode *ptr = q.front() ;
    		q.pop() ;
    		while (!q.empty())
    		{
    			ptr->next = s.top() ;
    			s.pop() ;
    			ptr = ptr->next ;
    
    			ptr->next = q.front() ;
    			q.pop() ;
    			ptr = ptr->next ;
    		}
    		while (!s.empty()) //一定有s.size() >= q.size()
    		{
    			ptr->next = s.top() ;
    			s.pop() ;
    			ptr = ptr->next ;
    		}
    
    		ptr->next = NULL ;
        }
    };
    
    ifstream in("data.txt") ;
    #define cin in
    
    int main(int argc, char **argv)
    {
    	ListNode *head = NULL;
    	ListNode *tail = head;
    	int tmpN;
    	while (cin >> tmpN)
    	{
    		ListNode *tmpNode = new ListNode(tmpN) ;
    		if (head == NULL)
    		{
    			head = tmpNode ;
    			tail = head ;
    		}
    		else
    		{
    			tail->next = tmpNode ;
    			tail = tmpNode ;
    		}
    	}
    
    	Solution s ;
    	s.reorderList(head) ;
    
    	ListNode *ptr = head ;
    	while (ptr)
    	{
    		cout << ptr->val << " " ;
    		ptr = ptr->next ;
    	}
    	cout << endl;
    
    	return 0 ;
    }

[My Submissions]: http://oj.leetcode.com/problems/reorder-list/submissions/