143. Reorder List
专业从事成都网站制作、成都网站设计,高端网站制作设计,小程序制作,网站推广的成都做网站的公司。优秀技术团队竭力真诚服务，采用H5网站设计+CSS3前端渲染技术，自适应网站建设，让网站在手机、平板、PC、微信下都能呈现。建站过程建立专项小组，与您实时在线互动，随时提供解决方案，畅聊想法和感受。
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}.
题意：
给定链表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）把第二部分链表插入到第一部分链表的指定位置即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void reorderList(struct ListNode* head)
{
if ( head == NULL || head->next == NULL || head->next->next == NULL )
{
return;
}
struct ListNode *list = head;
int len = 0;
while ( list )
{
list = list->next;
len += 1;
}
int key = 0;
if ( len % 2 == 0 )
{
key = len / 2;
}
else
{
key = (len / 2) + 1;
}
struct ListNode *second = head;
list = head;
int cnt = 0;
while ( cnt < key )
{
list = second;
second = second->next;
cnt += 1;
}
list->next = NULL;
list = NULL;
struct ListNode *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;
}
}
