143. Reorder List

專業(yè)從事成都網(wǎng)站制作、成都網(wǎng)站設(shè)計,高端網(wǎng)站制作設(shè)計,小程序制作,網(wǎng)站推廣的成都做網(wǎng)站的公司。優(yōu)秀技術(shù)團(tuán)隊竭力真誠服務(wù)，采用H5網(wǎng)站設(shè)計+CSS3前端渲染技術(shù)，自適應(yīng)網(wǎng)站建設(shè)，讓網(wǎng)站在手機、平板、PC、微信下都能呈現(xiàn)。建站過程建立專項小組，與您實時在線互動，隨時提供解決方案，暢聊想法和感受。

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）鏈表為空，或者鏈表只有一個或者兩個節(jié)點，直接返回即可。

2）獲取鏈表的長度len，把鏈表分成前后兩部分。如果長度為奇數(shù)，前部分鏈表長度為len/2 + 1，后部分長度為len/2。比如｛1，2，3，4，5｝拆分后前部分鏈表為｛1，2，3｝后部分鏈表為｛4，5｝；如果長度為偶數(shù)，前部分鏈表長度為len / 2 ，后部分長度為 len / 2。比如｛1，2，3，4，5，6｝拆分后為｛1，2，3｝和｛4，5，6｝

3）反轉(zhuǎn)第二部分鏈表。

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

網(wǎng)站名稱：[LeetCode]143.ReorderList
網(wǎng)站URL：http://aaarwkj.com/article10/jeejgo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、App開發(fā)、企業(yè)建站、網(wǎng)站策劃、全網(wǎng)營銷推廣、用戶體驗

廣告

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