Recorder-List

题目描述

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.将链表的中间结点及之后的结点push到一个栈中；
3.然后将栈中的结点重新插入到链表中相应的位置即可。

主要代码

class Solution {
public:
    void reorderList(ListNode *head) {
        stack<ListNode *> reverseStack;
        ListNode *p=head;
        ListNode *q=head;
        if(p!=NULL&&p->next!=NULL){
                while(q){//找到链表的中点
                    if(q->next){
                        q=q->next->next;
                    }
                    else{
                        q=q->next;
                    }
                    p=p->next;
                }
                while(p){
                    reverseStack.push(p);
                    p=p->next;
                }
                p=head;
                ListNode *nextNode;
                while(!reverseStack.empty()){
                    nextNode=p->next;
                    q=reverseStack.top();
                    p->next=q;
                    q->next=nextNode;
                    p=nextNode;
                    reverseStack.pop();
                }
                p->next=NULL;//这句不写会出错
        }
    }
};