題目描述
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.利用快慢指針炉媒，找到鏈表的中間結(jié)點(diǎn)诺苹；
2.將鏈表的中間結(jié)點(diǎn)及之后的結(jié)點(diǎn)push到一個(gè)棧中；
3.然后將棧中的結(jié)點(diǎn)重新插入到鏈表中相應(yīng)的位置即可。
主要代碼
class Solution {
public:
void reorderList(ListNode *head) {
stack<ListNode *> reverseStack;
ListNode *p=head;
ListNode *q=head;
if(p!=NULL&&p->next!=NULL){
while(q){//找到鏈表的中點(diǎn)
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;//這句不寫(xiě)會(huì)出錯(cuò)
}
}
};
