leetcode 328. Odd Even Linked List

Vultr 發布于2019-08-15 14:47 / 2316人閱讀

摘要：最后將奇數鏈表尾連到偶數鏈表頭即可。改進的思路在于減少額外的變量創建。奇數指針的初始值為，而偶數指針的初始值為。則下一個奇數值位于上，此時將該奇數指針移動到上之后，偶數指針的值則為。

題目要求

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.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->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 ...

將一個鏈表中的節點按照奇數位上的節點在前，偶數位上的節點在后重新排序。這里需要注意的是節點之間的相對順序不可以改變。即1->2->3->4不可以變為1->3->4->2，只能是1->3->2->4。

思路和代碼

首先想到的就是直接新建兩個鏈表頭分別用來從原始的鏈表中提取奇數位上的節點和偶數位上的節點。最后將奇數鏈表尾連到偶數鏈表頭即可。

    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummyOdd = new ListNode(0);
        ListNode dummyEven = new ListNode(0);
        ListNode cur = head,
                odd = dummyOdd,
                even = dummyEven;
        int count = 0;
        while(cur!=null){
            if(count%2==0){
                odd.next = cur;
                odd = odd.next;
                cur = cur.next;
            }else{
                even.next = cur;
                even = even.next;
                cur = cur.next;
            }
            count++;
        }
        odd.next = dummyEven.next;
        even.next = null;
        return dummyOdd.next;
    }

改進的思路在于減少額外的變量創建。這里我們其實可以借鑒雙指針的思路。偶數指針一次前進兩位，奇數指針一次前進兩位。奇數指針odd的初始值為head，而偶數指針even的初始值為head.next。則下一個奇數值位于even.next上，此時將該奇數指針移動到even.next上之后，偶數指針的值則為odd.next。

    public ListNode oddEvenList2(ListNode head) {
        if(head==null) return head;
        ListNode odd,even,evenStart;
        odd=head;
        even=head.next;
        evenStart=even;
        
        while(even!=null && even.next!=null){
            odd.next=even.next;
            odd=odd.next;
            even.next=odd.next;
            even=even.next; 
        }
        odd.next=evenStart;
        return head;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

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

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

[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
LeetCode 328：奇偶鏈表 Odd Even Linked List

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

yeooo 2019-08-16 18:38 評論0 收藏0
LeetCode 328：奇偶鏈表 Odd Even Linked List

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

flybywind 2019-07-31 11:29 評論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