題目一 力扣143.重排鏈表

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reorder-list/

1.描述

給定一個單鏈表L的頭節點head，單鏈表 L 表示為：
L0 → L1 → … → Ln - 1 → Ln
請將其重新排列后變為：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，

2.示例

• 示例 1：
  

輸入：head = [1,2,3,4]
輸出：[1,4,2,3]

• 示例2
  

輸入：head = [1,2,3,4,5]
輸出：[1,5,2,4,3]

解法一 線性化

解題思路

題目的要求是將從尾節點開始的后半部分，重新填充到從頭節點開始的前半部分，倒數第一個節點變更為正數第一個節點的后繼結點，倒數第二個節點變更為正數第二個節點的尾結點，倒數第三個節點變更為正數第三個節點的尾結點，，，依此類推，單鏈表的缺點是無法隨機訪問，只能順序訪問，于是我們可以考慮將單鏈表變更為可隨機訪問的線性表，然后再對節點進行操作即可，

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        vector<ListNode*> node;//存盤鏈表節點的線性表
        ListNode* temp = head;//訪問指標
        while(temp){//將單鏈表節點存盤到線性表中
            node.push_back(temp);
            temp = temp->next;
        }
        int m = node.size();//計算節點數
        for(int i = 0; i < m/2; ++i){
        //從i=0開始，將正數第i個節點的后繼結點更新為倒數第i個節點，
        //并將倒數第i+1個節點的后繼節點置為空
            node[m-i-2]->next=nullptr;
            node[m-i-1]->next=node[i]->next;
            node[i]->next=node[m-i-1];
        }
    }
};

復雜度分析

時間復雜度： O(m)，m為單鏈表節點數，遍歷整個單鏈表和修改next指標指向都需要O(m)時間，
空間復雜度： O(m)，輔助線性表的空間消耗，

解法二 雙指標+翻轉鏈表+鏈表合并

解題思路

解法一的時間復雜度已為最優，但是空間復雜度仍然可以優化，如果我們使用雙指標技術找到單鏈表后半段的頭結點，然后繼續使用雙指標技術原地翻轉單鏈表的后半段，最后繼續使用雙指標技術將鏈表前半段與翻轉后的單鏈表后半段原地合并，即可將空間復雜度優化至常數級，

代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        ListNode* headRight = findRight(head);
        if(!headRight) return;
        headRight = reverseList(headRight);
        mergeList(head,headRight);
    }

    ListNode* findRight(ListNode* head){//尋找鏈表后半段的開始節點
        ListNode* verySlow = head;//用于標記前半段鏈表尾結點的指標
        ListNode* slow = head;//慢指標，用于標記后半段鏈表頭結點
        ListNode* fast = head;//快指標
        int count = 0;//計數器
        while(fast){
            fast = fast->next;//移動快指標
            ++count;//計數器加一
            if(count%2==0){//每移動兩次快指標就移動一次慢指標
                slow =slow->next;
                if(verySlow->next != slow){//除了第一次移動慢指標以外，慢指標和更慢指標都一起移動
                    verySlow = verySlow->next;
                }
            }
        }
        if(count<=2) return nullptr;//如果鏈表長度低于3，回傳空指標，后續不作處理，直接結束程式
        if(count%2!=0){//如果鏈表節點數為奇數，慢指標和更慢指標都后移一位
            slow = slow->next;
            verySlow = verySlow->next;
        }
        verySlow->next = nullptr;//將更慢指標指向節點的后繼結點置為空，否則處理完畢后鏈表會有環
        return slow;
    }

    ListNode* reverseList(ListNode* head){//翻轉鏈表
        ListNode* pre = nullptr;//前驅節點
        ListNode* cur = head;//當前節點
        while(cur){
            ListNode* nextPtr = cur->next;//后繼節點
            cur->next = pre;//翻轉
            pre = cur;//更新前驅節點和當前節點
            cur = nextPtr;
        }
        return pre;//回傳翻轉后的鏈表
    }

    ListNode* mergeList(ListNode* left, ListNode* right){//合并兩個鏈表
        ListNode* node = left;//用于標記前半段鏈表節點
        while(right){
            ListNode*  temp = right->next;//后半段鏈表當前節點的后繼節點
            right->next = node->next;//將后半段鏈表當前節點置為前半段鏈表當前節點的后繼節點
            node->next = right;
            node = right->next;//移動指標
            right = temp;
        }
        return left;//回傳合并后的單鏈表
    }
};

復雜度分析

時間復雜度： O(m)，尋找后半段節點的頭結點，翻轉后半段鏈表，合并前后段鏈表均為O(m)時間，
空間復雜度： O(1)，只需常數個額外變數，

標籤：其他

上一篇：HashMap原理及原始碼分析

下一篇：線性表的基本操作