LeetCode 328：奇偶鏈表 Odd Even Linked List

flybywind 發布于2019-07-31 11:29 / 2222人閱讀

摘要：給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。需要記錄偶數位節點的第一個節點，因為這是偶數鏈表的頭節點，最后拼接鏈表時要用奇數鏈表的尾節點連接該節點。

?給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。

請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節點總數。

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

示例 1:

輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

示例 2:

輸入: 2->1->3->5->6->4->7->NULL 
輸出: 2->3->6->7->1->5->4->NULL

說明:

應當保持奇數節點和偶數節點的相對順序。

鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on ...

解題思路：

這道題很簡單，迭代鏈表，將該鏈表奇數位節點和偶數位節點分別取出分隔成兩個鏈表，然后將奇偶兩個鏈表連接起來組成新鏈表，返回頭節點即可。

需要記錄偶數位節點的第一個節點，因為這是偶數鏈表的頭節點，最后拼接鏈表時要用奇數鏈表的尾節點連接該節點。

你可以定義一個 int 型數值 i 為 0，每次迭代鏈表時 i 值自增 1 （i++），并判斷 i 值除以 2 的余數為奇偶（ i%2 ），以此為根據判斷該節點是添加到奇鏈表后還是偶鏈表后。缺點是每次都要給 i 做自增運算求余運算和判斷余數，這在鏈表很長時將會占用很長的時間。而且int型值上限為 2147483647 ，超過這個值需要額外考慮方法。

另外一種方法是以第一個奇偶節點開始，將奇節點指向偶節點的下一個節點（肯定是奇節點），然后刷新奇鏈表，此時奇節點指向新加入的節點；將偶節點指向奇節點的下一個節點（肯定是偶節點），然后刷新偶鏈表，此時偶節點指向新加入的節點；......以此類推直到遇到空節點。

Java：

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;//如果該鏈表內節點數在兩個及以下直接返回頭節點
        ListNode tmp = head.next;//暫存偶節點的第一個
        ListNode odd = head;//奇節點的第一個
        ListNode even = head.next;//偶節點的第一個
        while (even != null && even.next != null) {//循環條件，偶節點遇空時結束
            odd.next = even.next;//奇節點指向偶節點的下一個節點
            odd = odd.next;//刷新奇鏈表指針
            even.next = odd.next;//偶節點指向奇節點的下一個節點
            even = even.next;//刷新偶鏈表指針
        }
        odd.next = tmp;//連接雙鏈表
        return head;
    }
}

Python3：

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

歡迎關注公.眾號一起學習：愛寫Bug

GPU云服務器云服務器 Even linked Odd python odd

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/45193.html

LeetCode 328：奇偶鏈表 Odd Even Linked List

摘要：給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。需要記錄偶數位節點的第一個節點，因為這是偶數鏈表的頭節點，最后拼接鏈表時要用奇數鏈表的尾節點連接該節點。 ?給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。請嘗試使用原地算法完成...

yeooo 2019-08-16 18:38 評論0 收藏0
leetcode 328. Odd Even Linked List

摘要：最后將奇數鏈表尾連到偶數鏈表頭即可。改進的思路在于減少額外的變量創建。奇數指針的初始值為，而偶數指針的初始值為。則下一個奇數值位于上，此時將該奇數指針移動到上之后，偶數指針的值則為。題目要求 Given a singly linked list, group all odd nodes together followed by the even nodes. Please note...

Vultr 2019-08-15 14:47 評論0 收藏0
[LeetCode] 328. Odd Even Linked List

Problem Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do ...

Invoker 2019-08-16 14:28 評論0 收藏0
328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and notthe value in the nodes.You should try to do it in plac...

abson 2019-07-31 10:19 評論0 收藏0
[LeetCode/LintCode] Odd Even Linked List

Problem Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. Example Example:Given...

awokezhou 2019-08-16 12:44 評論0 收藏0