[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;
    }
}