成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode 328：奇偶鏈表 Odd Even Linked List

yeooo / 3241人閱讀

摘要：給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推。需要記錄偶數(shù)位節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)，因?yàn)檫@是偶數(shù)鏈表的頭節(jié)點(diǎn)，最后拼接鏈表時(shí)要用奇數(shù)鏈表的尾節(jié)點(diǎn)連接該節(jié)點(diǎn)。

?給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性，而不是節(jié)點(diǎn)的值的奇偶性。

請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點(diǎn)總數(shù)。

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

說明:

應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對順序。

鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推。

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 ...

解題思路：

這道題很簡單，迭代鏈表，將該鏈表奇數(shù)位節(jié)點(diǎn)和偶數(shù)位節(jié)點(diǎn)分別取出分隔成兩個(gè)鏈表，然后將奇偶兩個(gè)鏈表連接起來組成新鏈表，返回頭節(jié)點(diǎn)即可。

需要記錄偶數(shù)位節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)，因?yàn)檫@是偶數(shù)鏈表的頭節(jié)點(diǎn)，最后拼接鏈表時(shí)要用奇數(shù)鏈表的尾節(jié)點(diǎn)連接該節(jié)點(diǎn)。

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

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

Java： 
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;//如果該鏈表內(nèi)節(jié)點(diǎn)數(shù)在兩個(gè)及以下直接返回頭節(jié)點(diǎn)
        ListNode tmp = head.next;//暫存偶節(jié)點(diǎn)的第一個(gè)
        ListNode odd = head;//奇節(jié)點(diǎn)的第一個(gè)
        ListNode even = head.next;//偶節(jié)點(diǎn)的第一個(gè)
        while (even != null && even.next != null) {//循環(huán)條件，偶節(jié)點(diǎn)遇空時(shí)結(jié)束
            odd.next = even.next;//奇節(jié)點(diǎn)指向偶節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
            odd = odd.next;//刷新奇鏈表指針
            even.next = odd.next;//偶節(jié)點(diǎn)指向奇節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
            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

歡迎關(guān)注公.眾號(hào)一起學(xué)習(xí)：愛寫B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75490.html

相關(guān)文章

  • LeetCode 328：奇偶鏈表 Odd Even Linked List

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

    flybywind 評論0 收藏0

  • leetcode 328. Odd Even Linked List

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

    Vultr 評論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 評論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 評論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 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<