28
05/2015
[LeetCode] Reorder List
Reorder 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}.
解题思路：
这道题比较简单，弄清楚题意，然后链表操作即可。大体思路是，先计算链表长度，然后将链表一分为二。后半部分链表翻转，然后将两个链表合并。注意一些边界条件，比如，若链表长度为奇数，前一个链表多分一个；若为偶数，两个链表一样多。为简便起见，分别分配两个新表头。代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(head==NULL){
return;
}
int len = getListLength(head);
ListNode* head1 = new ListNode(0);
ListNode* head2= new ListNode(0); //head2表示后半部分倒转
head1->next = head;
ListNode* p = head1;
for(int i=(len+1)/2; i>0; i--){
p=p->next;
}
//此时p表示head1前一个节点
ListNode* q=p->next;
p->next=NULL;
//将后半部分翻转到head2中
while(q!=NULL){
p=q->next;
q->next=head2->next;
head2->next=q;
q=p;
}
//将两个链表合并
p=head1->next;
while(head2->next!=NULL){
q=head2->next;
head2->next = q->next;
q->next=p->next;
p->next=q;
p=q->next;
}
head=head1->next;
delete head1;
delete head2;
}
int getListLength(ListNode* head){
int len = 0;
while(head!=NULL){
len++;
head=head->next;
}
return len;
}
};转载请注明：康瑞部落 » [LeetCode] Reorder List
0 条评论