[[432017]]

重排鏈表

思路

本篇將給出三種C++實(shí)現(xiàn)的方法

• 數(shù)組模擬
• 雙向隊(duì)列模擬
• 直接分割鏈表

方法一

把鏈表放進(jìn)數(shù)組中，然后通過雙指針法，一前一后，來遍歷數(shù)組，構(gòu)造鏈表。

代碼如下：

class Solution { 
public: 
    void reorderList(ListNode* head) { 
        vector<ListNode*> vec; 
        ListNode* cur = head; 
        if (cur == nullptr) return; 
        while(cur != nullptr) { 
            vec.push_back(cur); 
            cur = cur->next; 
        } 
        cur = head; 
        int i = 1; 
        int j = vec.size() - 1;  // i j為之前前后的雙指針 
        int count = 0; // 計(jì)數(shù)，偶數(shù)去后面，奇數(shù)取前面 
        while (i <= j) { 
            if (count % 2 == 0) { 
                cur->next = vec[j]; 
                j--; 
            } else { 
                cur->next = vec[i]; 
                i++; 
            } 
            cur = cur->next; 
            count++; 
        } 
        cur->next = nullptr; // 注意結(jié)尾 
    } 
}; 

方法二

把鏈表放進(jìn)雙向隊(duì)列，然后通過雙向隊(duì)列一前一后彈出數(shù)據(jù)，來構(gòu)造新的鏈表。這種方法比操作數(shù)組容易一些，不用雙指針模擬一前一后了

class Solution { 
public: 
    void reorderList(ListNode* head) { 
        deque<ListNode*> que; 
        ListNode* cur = head; 
        if (cur == nullptr) return; 
 
        while(cur->next != nullptr) { 
            que.push_back(cur->next); 
            cur = cur->next; 
        } 
 
        cur = head; 
        int count = 0; // 計(jì)數(shù)，偶數(shù)去后面，奇數(shù)取前面 
        ListNode* node; 
        while(que.size()) { 
            if (count % 2 == 0) { 
                node = que.back(); 
                que.pop_back(); 
            } else { 
                node = que.front(); 
                que.pop_front(); 
            } 
            count++; 
            cur->next = node; 
            cur = cur->next; 
        } 
        cur->next = nullptr; // 注意結(jié)尾 
    } 
}; 

方法三

將鏈表分割成兩個(gè)鏈表，然后把第二個(gè)鏈表反轉(zhuǎn)，之后在通過兩個(gè)鏈表拼接成新的鏈表。

如圖：

這種方法，比較難，平均切割鏈表，看上去很簡單，真正代碼寫的時(shí)候有很多細(xì)節(jié)，同時(shí)兩個(gè)鏈表最后拼裝整一個(gè)新的鏈表也有一些細(xì)節(jié)需要注意!

代碼如下：

class Solution { 
private: 
    // 反轉(zhuǎn)鏈表 
    ListNode* reverseList(ListNode* head) { 
        ListNode* temp; // 保存cur的下一個(gè)節(jié)點(diǎn) 
        ListNode* cur = head; 
        ListNode* pre = NULL; 
        while(cur) { 
            temp = cur->next;  // 保存一下 cur的下一個(gè)節(jié)點(diǎn)，因?yàn)榻酉聛硪淖僣ur->next 
            cur->next = pre; // 翻轉(zhuǎn)操作 
            // 更新pre 和 cur指針 
            pre = cur; 
            cur = temp; 
        } 
        return pre; 
    } 
 
public: 
    void reorderList(ListNode* head) { 
        if (head == nullptr) return; 
        // 使用快慢指針法，將鏈表分成長度均等的兩個(gè)鏈表head1和head2 
        // 如果總鏈表長度為奇數(shù)，則head1相對(duì)head2多一個(gè)節(jié)點(diǎn) 
        ListNode* fast = head; 
        ListNode* slow = head; 
        while (fast && fast->next && fast->next->next) { 
            fast = fast->next->next; 
            slow = slow->next; 
        } 
        ListNode* head1 = head; 
        ListNode* head2; 
        head2 = slow->next; 
        slow->next = nullptr; 
 
        // 對(duì)head2進(jìn)行翻轉(zhuǎn) 
        head2 = reverseList(head2); 
 
        // 將head1和head2交替生成新的鏈表head 
        ListNode* cur1 = head1; 
        ListNode* cur2 = head2; 
        ListNode* cur = head; 
        cur1 = cur1->next; 
        int count = 0; // 偶數(shù)取head2的元素，奇數(shù)取head1的元素 
        while (cur1 && cur2) { 
            if (count % 2 == 0) { 
                cur->next = cur2; 
                cur2 = cur2->next; 
            } else { 
                cur->next = cur1; 
                cur1 = cur1->next; 
            } 
            count++; 
            cur = cur->next; 
        } 
        if (cur2 != nullptr) { // 處理結(jié)尾 
            cur->next = cur2; 
        } 
        if (cur1 != nullptr) { 
            cur->next = cur1; 
        } 
    } 
}; 

其他語言版本

Java

// 方法三 
public class ReorderList { 
    public void reorderList(ListNode head) { 
        ListNode fast = head, slow = head; 
        //求出中點(diǎn) 
        while (fast.next != null && fast.next.next != null) { 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
        //right就是右半部分 12345 就是45  1234 就是34 
        ListNode right = slow.next; 
        //斷開左部分和右部分 
        slow.next = null; 
        //反轉(zhuǎn)右部分 right就是反轉(zhuǎn)后右部分的起點(diǎn) 
        right = reverseList(right); 
        //左部分的起點(diǎn) 
        ListNode left = head; 
        //進(jìn)行左右部分來回連接 
        //這里左部分的節(jié)點(diǎn)個(gè)數(shù)一定大于等于右部分的節(jié)點(diǎn)個(gè)數(shù) 因此只判斷right即可 
        while (right != null) { 
            ListNode curLeft = left.next; 
            left.next = right; 
            left = curLeft; 
 
            ListNode curRight = right.next; 
            right.next = left; 
            right = curRight; 
        } 
    } 
 
    public ListNode reverseList(ListNode head) { 
        ListNode headNode = new ListNode(0); 
        ListNode cur = head; 
        ListNode next = null; 
        while (cur != null) { 
            next = cur.next; 
            cur.next = headNode.next; 
            headNode.next = cur; 
            cur = next; 
        } 
        return headNode.next; 
    } 
} 
 
// 方法一 Java實(shí)現(xiàn)，使用數(shù)組存儲(chǔ)節(jié)點(diǎn) 
 class Solution { 
    public void reorderList(ListNode head) { 
        // 雙指針的做法 
        ListNode cur = head; 
        // ArrayList底層是數(shù)組，可以使用下標(biāo)隨機(jī)訪問 
        List<ListNode> list = new ArrayList<>(); 
        while (cur != null){ 
            list.add(cur); 
            cur = cur.next; 
        } 
        cur = head;  // 重新回到頭部 
        int l = 1, r = list.size() - 1;  // 注意左邊是從1開始 
        int count = 0; 
        while (l <= r){ 
            if (count % 2 == 0){ 
                // 偶數(shù) 
                cur.next = list.get(r); 
                r--; 
            }else { 
                // 奇數(shù) 
                cur.next = list.get(l); 
                l++; 
            } 
            // 每一次指針都需要移動(dòng) 
            cur = cur.next; 
            count++; 
        } 
        // 注意結(jié)尾要結(jié)束一波 
        cur.next = null; 
    } 
} 
// 方法二：使用雙端隊(duì)列，簡化了數(shù)組的操作，代碼相對(duì)于前者更簡潔（避免一些邊界條件） 
class Solution { 
    public void reorderList(ListNode head) { 
        // 使用雙端隊(duì)列的方法來解決 
        Deque<ListNode> de = new LinkedList<>(); 
        // 這里是取head的下一個(gè)節(jié)點(diǎn)，head不需要再入隊(duì)了，避免造成重復(fù) 
        ListNode cur = head.next; 
        while (cur != null){ 
            de.offer(cur); 
            cur = cur.next; 
        } 
        cur = head;  // 回到頭部 
 
        int count = 0; 
        while (!de.isEmpty()){ 
            if (count % 2 == 0){ 
                // 偶數(shù)，取出隊(duì)列右邊尾部的值 
                cur.next = de.pollLast(); 
            }else { 
                // 奇數(shù)，取出隊(duì)列左邊頭部的值 
                cur.next = de.poll(); 
            } 
            cur  = cur.next; 
            count++; 
        } 
        cur.next = null; 
    } 
} 

 Python

# 方法二 雙向隊(duì)列 
class Solution: 
    def reorderList(self, head: ListNode) -> None: 
        """ 
        Do not return anything, modify head in-place instead. 
        """ 
        d = collections.deque() 
        tmp = head 
        while tmp.next: # 鏈表除了首元素全部加入雙向隊(duì)列 
            d.append(tmp.next) 
            tmp = tmp.next 
        tmp = head 
        while len(d): # 一后一前加入鏈表 
            tmp.next = d.pop() 
            tmp = tmp.next 
            if len(d): 
                tmp.next = d.popleft() 
                tmp = tmp.next 
        tmp.next = None # 尾部置空 
 
# 方法三 反轉(zhuǎn)鏈表 
class Solution: 
    def reorderList(self, head: ListNode) -> None: 
        if head == None or head.next == None: 
            return True 
        slow, fast = head, head 
        while fast and fast.next: 
            slow = slow.next 
            fast = fast.next.next 
        right = slow.next # 分割右半邊 
        slow.next = None # 切斷 
        right = self.reverseList(right) #反轉(zhuǎn)右半邊 
        left = head 
        # 左半邊一定比右半邊長, 因此判斷右半邊即可 
        while right: 
            curLeft = left.next 
            left.next = right 
            left = curLeft 
 
            curRight = right.next 
            right.next = left 
            right = curRight 
 
 
    def reverseList(self, head: ListNode) -> ListNode: 
        cur = head 
        pre = None 
        while(cur!=None): 
            temp = cur.next # 保存一下cur的下一個(gè)節(jié)點(diǎn) 
            cur.next = pre # 反轉(zhuǎn) 
            pre = cur 
            cur = temp 
        return pre