LeetCode 328——奇偶链表(JAVA)
发布时间:2020-12-15 05:31:20 所属栏目:Java 来源:网络整理
导读:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 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 说明:
直接上代码: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode oddEvenList(ListNode head) { if(head==null) return null; if(head.next==null||head.next.next==null) return head; ListNode odd=head; ListNode even=head.next; ListNode evenhead=even;//此处的evenhead是链表奇偶化之后偶半链的第一个节点,在下买你的while循环中,evenhead一直处于无前驱节点状态 while(odd.next!=null&&even.next!=null){ odd.next=odd.next.next; even.next=even.next.next; odd=odd.next; even=even.next; }//经过while循环之后,实际上链表已经被切成两半了,一般是奇链表,一半是偶链表,其中保留了两个指针,一个是odd奇链表的最后一个元素,evenhead是偶链表的第一个节点。 odd.next=evenhead;//将奇偶链表连接起来 return head; } } 算法思想: 1、根据奇偶数原则,首先将odd指向head,even指向head.next,同时evenhead也指向head.next。 2、接下来,分别以odd开头“删除”偶数链表,以even 开头删除奇数链表。这样一来将整个链表拆分为两个链表。同时保留了三个节点,分别是odd(奇数链表的最后一个节点),even(偶数链表最后一个节点),evenhead(偶数链表第一个节点)。 3、最后只需将奇偶链表连接起来即可。odd.next=evenhead,大功告成!!! 算法分析: 此算法是在原地修改,并没有开辟新的存储空间,因此空间复杂度是O(1); 对于时间复杂度来说,需要迭代整个链表,因此时间复杂度是O(nodes)。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 在java cross-plateform-ably中没有时间播种随机发生器
- java – jsonpath查找所有对象(restassured)
- java – 在JTextPane中禁用Word换行
- JSP jsp:params:多参数赋值标签
- java – 在我的主代码中使用Thread.currentThread.sleep()有
- Java-maven-shangcheng-manager-配置
- Spring Security使用中Preflight请求和跨域问题详解
- java – 使用new关键字创建的Spring bean(@Component)中的自
- java – 仅使用辅助全局索引查询Dynamo表
- 在Java中绘制一个漂亮的圆圈