开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 328】奇偶链表

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

题目描述


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

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例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

提示

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

题解


本题要求使用原地算法,也就是不允许额外新建一个链表,只能使用常数的空间复杂度来实现。

要把奇数位置串起来,再把偶数位置串起来,最后把偶数位置链表接到奇数位置链表末尾。因为 head 表示的就是奇数位置链表的第一个结点,所以我们只需要再新建一个变量 even_head 指向 head->next ,也就是偶数位置链表的第一个结点。

此外还需要新建两个指针 oddeven 分别指向当前遍历到的奇偶结点,初始时分别指向奇偶头结点。

接下来只需要分成奇偶两条链,各自串联下去就行了。也就是每次把 odd->next 指向 odd->next->next ,把 even->next 指向 even->next->next 。也就是隔了一个元素,把当前结点下一个结点指向它的下一个和它奇偶位置相同的结点。注意的是,这里一定要先改变 even->next ,再改变 odd->next 。因为 odd 是在 even 前一个的,先改变它指向的下一个元素并不会影响 even 后面的元素。但是如果你先改变了 even 指向的下一个元素,那么 odd->next->next 就变了,就无法指向正确的结点了。

如果我们换个写法,先把 odd->next 指向 even->next ,再把 even->next 指向 even->next->next ,你就能很清楚的看出来了,必须先改变 odd->next ,因为它依赖于 even->next

最后把 odd 指向 odd->next ,把 even 指向 even->next ,继续遍历下一个结点。

什么时候停止呢?链表的最后一个结点要么是奇数结点,要么是偶数结点。如果是偶数结点,那么最后 even 不为空,但是它的下一个结点 even->next 为空,这时候结束遍历。如果是奇数结点,那么最后 odd 不为空,但是 even 为空,那么也结束遍历。综上,如果 even 或者 even->next 为空的时候,结束遍历。

最后只需要把 odd 的下一个结点指向 even_head 就能把两个链表串起来了。image.png

代码


c++

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    public:  
    ListNode* oddEvenList(ListNode* head) {  
        if (head == NULL) return NULL;  
        ListNode* even_head = head->next;  
        ListNode* odd = head;     
        ListNode* even = head->next; 
        while (even && even->next) {   
            odd->next = even->next;    
            even->next = even->next->next;     
            odd = odd->next;     
            even = even->next;   
        }    
        odd->next = even_head;
        return head;  
    }
};

python

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = None
class Solution: 
    def oddEvenList(self, head: ListNode) -> ListNode: 
        if head is None: 
            return head   
        even_head, odd, even = head.next, head, head.next   
        while even is not None and even.next is not None: 
            odd.next = even.next   
            even.next = even.next.next    
            odd = odd.next    
            even = even.next   
            odd.next = even_head   
            return head

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


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

相关文章
从0到1搭建前端异常监控系统(Vue + Webpack + Node.js + Egg.js + Jest)(上)
从0到1搭建前端异常监控系统(Vue + Webpack + Node.js + Egg.js + Jest)
103 0
从0到1搭建前端异常监控系统(Vue + Webpack + Node.js + Egg.js + Jest)(下)
从0到1搭建前端异常监控系统(Vue + Webpack + Node.js + Egg.js + Jest)
22 0
Java调用opencv聚类算法kmeans
Java调用opencv聚类算法kmeans
36 0
leetcode算法228.汇总区间
如何用leetcode算法228.汇总区间?本文带大家解决这个问题。
26 0
再也不怕复现论文!arXiv携手Papers with Code,提交论文+上传代码一步到位
昨日,Papers with Code宣布,arXiv网站将允许研究人员在提交论文的同时提交代码,让所有感兴趣的人可以轻松地分析、审查或者复制最先进的人工智能技术及其取得的新进展。
77 0
召奴的大哉问系列:B2B 是否要做AB Test
AB Testing在软体工程领域是一个耳熟能详的词,大家都知道AB Test的重要性。当产品经理提出的需求不合里(太难做)时,程序员们心理总是os,你怎么知道客户到底要什么,不也是拍脑袋想的吗,这时候我们可能会提出另一种作法,并要求他(她)去做一个AB Test来验证哪一个作法更好。 但是,大家可能不知道,要做一个成功的AB Test实验,它背后的成本是非常巨大的。首先,你必须做许多的分析,了
675 0
LeetCode 328:奇偶链表 Odd Even Linked List
​给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
591 0
【阿里云资讯】2016 杭州 · 云栖大会 | 阿里云安全算法挑战赛决赛 同时拉开帷幕
今天,首届阿里云安全算法挑战赛决赛,与2016杭州 · 云栖大会同时开幕。当数万人与马云老师一起,云栖小镇共同见证飞天 · 进化的同时,阿里云的15支最强安全算法战队,在西溪园区蓄势待发。
4911 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载