leetCode-143:Reorder List

问题描述

给定一个链表,用 L0→L1→…→Ln-1→Ln 表示,要求在不改变节点值的情况下将链表改成以下顺序:L0→Ln→L1→Ln-1→L2→Ln-2→…。题目链接:点我

样例输入输出

输入:1->2->3->4

输出:1->4->2->3

输入:1->2->3->4->5

输出:1->5->2->4->3

问题解法

此题最简单的解法就是遍历一遍,在遍历过程中用一个数组来存储每个节点,然后遍历数组中的节点,根据规则将每个节点的 next 指针指向对应节点即可。但是这种做法需要花费 O(n) 的空间复杂度。一般而言,leetcode 上链表的题目,都是用 O(1) 的空间复杂度进行求解的。针对此题,一种 O(1)的空间复杂度的解法如下:

  • 首先将链表对半拆分,拆成两个子链表。可以用快慢指针进行拆分,时间复杂度为 O(n),空间复杂度为 O(1)
  • 其次,对后半部分的链接进行倒序。时间复杂度为 O(n),空间复杂度为 O(1)

  • 最后,合并前后两个子链表。时间复杂度为 O(n),空间复杂度为 O(1)

总体而言,时间复杂度为 O(n),空间复杂度为 O(1)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution
{
public void reorderList(ListNode head)
{
if (head == null || head.next == null)
{
return;
}

// split the list
ListNode half = head;
ListNode next = head;
ListNode prevEnd = head;
while (next != null && next.next != null)
{
next = next.next.next;
prevEnd = half;
half = half.next;
}
prevEnd.next = null;

// reverse the post half list
ListNode postHead = reverseList(half);

// merge two half list
mergeList(head, postHead);
}

private void mergeList(ListNode firstHead, ListNode secondHead)
{
ListNode first = firstHead;
ListNode second = secondHead;
while (first != null && first.next != null)
{
ListNode secondNext = second.next;
second.next = first.next;
first.next = second;
first = second.next;
second = secondNext;
}
first.next = second;
}

private ListNode reverseList(ListNode head)
{
ListNode dummyNode = new ListNode(-1, head);
while (head.next != null)
{
ListNode next = head.next;
head.next = next.next;
next.next = dummyNode.next;
dummyNode.next = next;
}

return dummyNode.next;
}
}