响应式自助建站平台,推广网站挣钱 优帮云,网站建设与服务考试,wordpress版本回退文章目录 Reorder List 重排链表问题描述#xff1a;分析代码PointerReverseMerge Tag Reorder List 重排链表
问题描述#xff1a;
给定一个单链表 L 的头节点 head #xff0c;单链表 L 表示为#xff1a;
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为#… 文章目录 Reorder List 重排链表问题描述分析代码PointerReverseMerge Tag Reorder List 重排链表
问题描述
给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 链表的长度范围为 [ 1 , 5 ∗ 1 0 4 ] 1 n o d e . v a l 1000 链表的长度范围为 [1, 5 * 10^4]\\ 1 node.val 1000 链表的长度范围为[1,5∗104]1node.val1000
分析 仔细观察可以发现最终的链表是呈现交替穿插的。 所以最简单的方式就是双端队列。 将所有节点依次入队然后分别从2端点取节点完成链接然后继续从队列中取节点补在之前的节点后面。 时间复杂度 O ( N ) O(N) O(N) ,空间复杂度 O ( N ) O(N) O(N). 只要熟悉双端队列会操作链表节点插入基本就可以。
还有一种思路是空间为 O ( 1 ) O(1) O(1)的。可以将链表拆成2段然后将后段反转然后进行合并。
所以需要知道从哪里拆可以使用快慢指针或者是简单遍历计数。还要知道如何反转链表可以递归或者是头插或者是顺序逆转。
时间复杂度 O ( N ) O(N) O(N) ,空间复杂度 O ( 1 ) O(1) O(1).
代码 PointerReverseMerge
public void reorderList(ListNode head) {if(headnull||head.nextnull) return ;ListNode h1 new ListNode(-1);h1.next head;ListNode f h1,s h1;while(f!nullf.next!null){s s.next;f f.next.next;}ListNode h2 new ListNode(-1);h2.next s.next;s.next null; // break listListNode p h2.next;h2.next null;while(p!null){ListNode t p;p p.next;t.next h2.next;h2.next t;} ListNode h3 new ListNode(-1);ListNode p1 h1.next,p2 h2.next,p3 h3; while(p1!null){if(p1!null){p3.next p1;p1 p1.next;p3 p3.next; }if(p2!null){p3.next p2;p2 p2.next;p3 p3.next;}}return;}时间复杂度 O ( N ) O(N) O(N)
空间复杂度 O ( 1 ) O(1) O(1)
Tag
LinkedList
Two Pointers
