143. Reorder List

Given a singly linked listL: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}.


题意：

给定链表L0→L1→…→Ln-1→Ln,重新整理后输出L0→Ln→L1→Ln-1→L2→Ln-2→…链表。

举例如下：给定链表｛1，2，3，4，5｝重排后为｛1，5，2，4，3｝

{1，2，3，4，5，6}重排后为｛1，6，2，5，3，4｝


思路：

1）链表为空，或者链表只有一个或者两个节点，直接返回即可。

2）获取链表的长度len，把链表分成前后两部分。如果长度为奇数，前部分链表长度为len/2 + 1，后部分长度为len/2。比如｛1，2，3，4，5｝拆分后前部分链表为｛1，2，3｝后部分链表为｛4，5｝；如果长度为偶数，前部分链表长度为len / 2 ，后部分长度为 len / 2。比如｛1，2，3，4，5，6｝拆分后为｛1，2，3｝和｛4，5，6｝

3）反转第二部分链表。

4）把第二部分链表插入到第一部分链表的指定位置即可。

/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/voidreorderList(structListNode*head){if(head==NULL||head->next==NULL||head->next->next==NULL){return;}structListNode*list=head;intlen=0;while(list){list=list->next;len+=1;}intkey=0;if(len%2==0){key=len/2;}else{key=(len/2)+1;}structListNode*second=head;list=head;intcnt=0;while(cnt<key){list=second;second=second->next;cnt+=1;}list->next=NULL;list=NULL;structListNode*next=NULL;while(second){next=second->next;second->next=list;list=second;second=next;}second=list;next=NULL;while(second){next=second;second=second->next;next->next=head->next;head->next=next;head=head->next->next;}}