题目:重排链表
Description
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
Sample
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
Solution
每次取当前第一个和最后一个节点,重新连接,得到多条两个节点的链(总节点数为奇数时有一条一个节点的链),按要求串起来,即可! 注意尾节点指针域指向空!
AC Code
class Solution {
public:
void reorderList(ListNode
* head
) {
if(head
==NULL||head
->next
==NULL||head
->next
->next
==NULL) return;
stack
<ListNode
*> s
;
queue
<ListNode
*> q
;
int num
=0;
ListNode
* temp
= head
;
while(temp
){
num
++;
s
.push(temp
);
q
.push(temp
);
temp
=temp
->next
;
}
stack
<ListNode
*> t
;
ListNode
* a
,*b
,*c
,*d
;
for(int i
=0;i
<num
/2;i
++){
a
=q
.front();
q
.pop();
b
=s
.top();
s
.pop();
a
->next
=b
;
if(!t
.empty()){
c
=t
.top();
c
->next
=a
;
}
t
.push(b
);
}
if(num
%2){
c
=t
.top();
d
=s
.top();
c
->next
= d
;
d
->next
=NULL;
}
else b
->next
=NULL;
return;
}
};
