LeetCode :
Reorder List
LeetCode上有下面这样一个题目，比较有意思，拿来实现，权当练习基本功了：
Reorder List
Total Accepted: 8598 Total
Submissions: 44508My 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 ;
}