LeetCode 328:奇偶链表 Odd Even Linked List-阿里云开发者社区

开发者社区> 爱写Bug> 正文

LeetCode 328:奇偶链表 Odd Even Linked List

简介: ​给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
+关注继续查看

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

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6935 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
2876 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4504 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7772 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
5466 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
9435 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
2147 0
+关注
爱写Bug
欢迎关注公众号:爱写Bug
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载