leetcode_reorder-list

题目：

Given a singly linked list L: L 0→L 1→…→L n-1→L n,reorder it to: L 0→L n →L 1→L n-1→L 2→L n-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}

思路：首先，通过快慢指针找到链表的中间结点；然后将链表分为两部分；其次，对后半部分的链表进行反排序；最后，将两部分链表进行合并。

相关实现：

（1）快慢指针找到中间链表：

1 ListNode *fast=head;
2 ListNode *slow=head;
3 while(fast!=NULL && fast->next!=NULL)     //另一种写法是：while(fast->next!=NULL && fast->next->next!=NULL)
4 {
5         fast = fast->next->next;
6         slow = slow->next;
7 }
   return slow;    //按照第一种写法，当结点为偶数个时，slow指向中间偏右的结点；对于第二种写法，则指向中间偏左的结点。当结点个数为奇数个时，两种写法都一样。

（2）拆分链表（按照第二种写法）

1 ListNode *tmp = slow->next;
2 slow->next = NULL;
3 slow = tmp;

(3)对第二部分链表反转

1 ListNode *node = slow->next;
2 slow->next = NULL;
3 while(node!=NULL)
4 {
5    tmp= node->next;
6    node->next = slow;
7   slow = node;
8   node = tmp;
9 }

(4)将两部分链表合并

 1 ListNode *p = head;
 2 ListNode *q = slow;
 3 ListNode *tmp;
 4 while(p!=NULL && q!=NULL )
 5 {
 6    tmp = p->next;
 7    p->next = q;
 8   p = tmp;
 9   tmp = q->next;
10    q->next = p;
11   q = tmp;
12 }