首页 > 代码库 > Leetcode: Reorder List

Leetcode: Reorder List

2024-07-21 12:20:13   219人阅读

Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You must do this in-place without altering the nodes‘ values.For example,Given {1,2,3,4}, reorder it to {1,4,2,3}.

这是一道比较综合的链表操作的题目，要按照题目要求给链表重新连接成要求的结果。其实理清思路也比较简单，分三步完成：（1）将链表切成两半，也就是找到中点，然后截成两条链表；（2）将后面一条链表进行reverse操作，就是反转过来；（3）将两条链表按顺序依次merge起来。

这几个操作都是我们曾经接触过的操作了，第一步找中点就是用runner technique方法，一个两倍速跑，一个一倍速跑，知道快的碰到链表尾部，慢的就正好停在中点了。第二步是比较常见的reverse操作，在Reverse Nodes in k-Group也有用到了，一般就是一个个的翻转过来即可。第三步是一个merge操作，做法类似于Sort List中的merge

接下来看看时间复杂度，第一步扫描链表一遍，是O(n)，第二步对半条链表做一次反转，也是O(n)，第三部对两条半链表进行合并，也是一遍O(n)。所以总的时间复杂度还是O(n)，由于过程中没有用到额外空间，所以空间复杂度O(1)。代码如下：

 1 /** 2  * Definition for singly-linked list. 3  * class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public void reorderList(ListNode head) {14         if (head == null || head.next == null) return;15         ListNode dummy = new ListNode(-1);16         dummy.next = head;17         ListNode current = dummy;18         ListNode runner = dummy;19         while (runner.next != null && runner.next.next != null) {20             current = current.next;21             runner = runner.next.next;22         }23         ListNode half = current.next;24         current.next = null;25         26         /*reverse the second Linked List*/27         if (runner.next != null) runner = runner.next; //make sure the runner pointer points to the end of the the second Linked List28         ListNode dummy2 = new ListNode(-2);29         dummy2.next = half;//create another dummy node whose next points to the head of the second Linked List30         while (dummy2.next != runner) {31             ListNode dnext = dummy2.next.next;32             ListNode rnext = runner.next;33             dummy2.next.next = rnext;34             runner.next = dummy2.next;35             dummy2.next = dnext;36         }37         38         /*merge the two Linked List together*/39         ListNode header1 = dummy;40         ListNode header2 = dummy2;41         while (header1.next != null && header2.next != null) {42             ListNode store = header1.next.next;43             ListNode merge = new ListNode(header2.next.val);44             header1.next.next = merge;45             merge.next = store;46             header1 = header1.next.next;47             header2 = header2.next;48         }49         if (header2.next != null) {50             header1.next = header2.next;51         }52     }53 }

 

Leetcode: Reorder List


联系
我们