leetcode 328. Odd Even Linked List

Vultr 发布于2019-08-15 14:47 / 2296人阅读

摘要：最后将奇数链表尾连到偶数链表头即可。改进的思路在于减少额外的变量创建。奇数指针的初始值为，而偶数指针的初始值为。则下一个奇数值位于上，此时将该奇数指针移动到上之后，偶数指针的值则为。

题目要求

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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