专栏首页爱写BugLeetCode 328:奇偶链表 Odd Even Linked List
原创

LeetCode 328:奇偶链表 Odd Even Linked List

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 328:奇偶链表 Odd Even Linked List

    给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 328:奇偶链表 Odd Even Linked List

    给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

    爱写bug
  • 数据结构与算法之美——链表

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2141593
  • 数据结构与算法学习笔记之写链表代码的正确姿势(下)

    将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。

    Dawnzhang
  • 数据结构之链表

    1、线性数据结构,动态数组、栈、队列,底层依托静态数组,靠resize解决固定容量问题。

    别先生
  • 剑指Offer-反转链表

    题目描述 输入一个链表,反转链表后,输出链表的所有元素。 思路 思路一: 迭代:将当前节点和下一节点保存起来,然后将当前节点反转。 思路二: 递归:利用递归走到...

    武培轩
  • 结构与算法(03):单向链表和双向链表

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,节点可以在运行时动态生成,节点包括两...

    知了一笑
  • Java实现单向链表

    一、前言 最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~ 本...

    Java3y

扫码关注云+社区

领取腾讯云代金券