提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode: Reorder List && Summary: Reverse a LinkedList

ampLeetCodeList reverse LinkedList Summary
2023-09-11 14:14:08 时间 
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 class Solution {
 2     public void reorderList(ListNode head) {
 3         if (head == null) return;
 4         ListNode dummy = new ListNode(-1);
 5         dummy.next = head;
 6         ListNode p1 = dummy, p2 = dummy;
 7         while (p2 != null && p2.next != null) {
 8             p2 = p2.next.next;
 9             p1 = p1.next;
10         }
11         ListNode head2 = p1.next;
12         p1.next = null;
13         ListNode head2New = reverse(head2);
14         merge(head, head2New);
15     }
16     
17     public ListNode reverse(ListNode head) {
18         if (head == null) return null;
19         ListNode p1 = head;
20         ListNode p2 = head.next;
21         while (p2 != null) {
22             ListNode next = p2.next;
23             p2.next = p1;
24             p1 = p2;
25             p2 = next;
26         }
27         head.next = null;
28         return p1;
29     }
30     
31     public ListNode merge(ListNode l1, ListNode l2) {
32         if (l2 == null) return l1;
33         int counter = 0;
34         ListNode pre = new ListNode(-1);
35         ListNode cur = pre;
36         while (l1 != null && l2 != null) {
37             if (counter % 2 == 0) {
38                 cur.next = l1;
39                 l1 = l1.next;
40             }
41             else {
42                 cur.next = l2;
43                 l2 = l2.next;
44             }
45             cur = cur.next;
46             counter ++;
47         }
48         cur.next = l1 != null ? l1 : l2;
49         return pre.next;
50     }
51 }

 

相关文章