[LeetCode]143. Reorder List

143. 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}.

题意：

给定链表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;
    }
}