其他系列文章導(dǎo)航

Java基礎(chǔ)合集
數(shù)據(jù)結(jié)構(gòu)與算法合集

設(shè)計模式合集

多線程合集

分布式合集

ES合集

文章目錄

其他系列文章導(dǎo)航

文章目錄

前言

一、題目描述

二、題解

2.1?方法一：分離節(jié)點后合并

三、代碼

3.1?方法一：分離節(jié)點后合并

四、復(fù)雜度分析

4.1?方法一：分離節(jié)點后合并

前言

這是力扣的 328 題，難度為中等，解題方案有很多種，本文講解我認為最奇妙的一種。

慢慢開始鏈表的模塊了，這道題是一道非常好的隊列的例題，很有代表性。

一、題目描述

給定單鏈表的頭節(jié)點?head?，將所有索引為奇數(shù)的節(jié)點和索引為偶數(shù)的節(jié)點分別組合在一起，然后返回重新排序的列表。

第一個節(jié)點的索引被認為是?奇數(shù)?，?第二個節(jié)點的索引為?偶數(shù)?，以此類推。

請注意，偶數(shù)組和奇數(shù)組內(nèi)部的相對順序應(yīng)該與輸入時保持一致。

你必須在?O(1)?的額外空間復(fù)雜度和?O(n)?的時間復(fù)雜度下解決這個問題。

示例 1:

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

示例 2:

輸入: head = [2,1,3,5,6,4,7]
輸出: [2,3,6,7,1,5,4]

提示:

• n ==??鏈表中的節(jié)點數(shù)
• 0 <= n <= 104
• -106?<= Node.val <= 106

二、題解

2.1?方法一：分離節(jié)點后合并

思路與算法：

如果鏈表為空，則直接返回鏈表。

對于原始鏈表，每個節(jié)點都是奇數(shù)節(jié)點或偶數(shù)節(jié)點。頭節(jié)點是奇數(shù)節(jié)點，頭節(jié)點的后一個節(jié)點是偶數(shù)節(jié)點，相鄰節(jié)點的奇偶性不同。因此可以將奇數(shù)節(jié)點和偶數(shù)節(jié)點分離成奇數(shù)鏈表和偶數(shù)鏈表，然后將偶數(shù)鏈表連接在奇數(shù)鏈表之后，合并后的鏈表即為結(jié)果鏈表。

原始鏈表的頭節(jié)點 head 也是奇數(shù)鏈表的頭節(jié)點以及結(jié)果鏈表的頭節(jié)點，head 的后一個節(jié)點是偶數(shù)鏈表的頭節(jié)點。令 evenHead = head.next，則 evenHead 是偶數(shù)鏈表的頭節(jié)點。

維護兩個指針 odd 和 even 分別指向奇數(shù)節(jié)點和偶數(shù)節(jié)點，初始時 odd = head，even = evenHead。通過迭代的方式將奇數(shù)節(jié)點和偶數(shù)節(jié)點分離成兩個鏈表，每一步首先更新奇數(shù)節(jié)點，然后更新偶數(shù)節(jié)點。

• 更新奇數(shù)節(jié)點時，奇數(shù)節(jié)點的后一個節(jié)點需要指向偶數(shù)節(jié)點的后一個節(jié)點，因此令 odd.next = even.next，然后令 odd = odd.next，此時 odd 變成 even 的后一個節(jié)點。
• 更新偶數(shù)節(jié)點時，偶數(shù)節(jié)點的后一個節(jié)點需要指向奇數(shù)節(jié)點的后一個節(jié)點，因此令 even.next = odd.next，然后令 even = even.next，此時 even 變成 odd 的后一個節(jié)點。

在上述操作之后，即完成了對一個奇數(shù)節(jié)點和一個偶數(shù)節(jié)點的分離。重復(fù)上述操作，直到全部節(jié)點分離完畢。全部節(jié)點分離完畢的條件是 even 為空節(jié)點或者 even.next 為空節(jié)點，此時 odd 指向最后一個奇數(shù)節(jié)點（即奇數(shù)鏈表的最后一個節(jié)點）。

最后令 odd.next = evenHead，將偶數(shù)鏈表連接在奇數(shù)鏈表之后，即完成了奇數(shù)鏈表和偶數(shù)鏈表的合并，結(jié)果鏈表的頭節(jié)點仍然是 head。

如下圖所示：

三、代碼

3.1?方法一：分離節(jié)點后合并

Java版本：

class Solution {    
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

C++版本：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* evenHead = head->next;
        ListNode* odd = head;
        ListNode* even = evenHead;
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

Python版本：

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        evenHead = head.next
        odd, even = head, evenHead
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head

Go版本：文章來源地址http://www.zghlxwxcb.cn/news/detail-808604.html

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    evenHead := head.Next
    odd := head
    even := evenHead
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = evenHead
    return head
}

四、復(fù)雜度分析

4.1?方法一：分離節(jié)點后合并

• 時間復(fù)雜度：O(n)，其中 n?是鏈表的節(jié)點數(shù)。需要遍歷鏈表中的每個節(jié)點，并更新指針。
• 空間復(fù)雜度：O(1)。只需要維護有限的指針。

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)和算法】奇偶鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！