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; ListNode *cur=head,*mid=head,*midnext,*midnextnext; while(cur){ cur=cur->next; if(cur)cur=cur->next; else break; if(cur)mid=mid->next; } midnext=mid->next; while(midnext&&midnext->next){ midnextnext=midnext->next; midnext->next=midnextnext->next; midnextnext->next=mid->next; mid->next=midnextnext; } cur=head; while(cur!=mid){ midnext=mid->next; mid->next=midnext->next; midnext->next=cur->next; cur->next=midnext; cur=midnext->next; } } };