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

網站名稱：[LeetCode]143.ReorderList
網站URL：http://m.newbst.com/article10/jeejgo.html

成都網站建設公司_創新互聯，為您提供品牌網站制作、App開發、企業建站、網站策劃、全網營銷推廣、用戶體驗

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯