143. 重排链表

1. 题目

  • 给定一个单链表 L 的头节点 head ，单链表 L 表示为：

    1
    L0 → L1 → … → Ln - 1 → Ln

    请将其重新排列后变为：

    1
    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

    不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

    示例 1：

    img

    1
    2
    输入：head = [1,2,3,4]
    输出：[1,4,2,3]

    示例 2：

    img

    1
    2
    输入：head = [1,2,3,4,5]
    输出：[1,5,2,4,3]

    提示：

    • 链表的长度范围为 [1, 5 * 104]
    • 1 <= node.val <= 1000

2. 思路

a. 栈 & 队列

  • 依赖栈的”先进后出“和队列的”先进先出“特性，遍历一次原始链表，将节点分别写入栈变量leftQueue和队列变量rightStack中
  • 依赖着上述写入的leftQueue和rightStack俩集合特性和上述遍历的链表长度，使用遍历下标配合算术取余特性分别：
    • 当索引下标对2取余结果为奇数时，从队列取出节点（此处取出的依次是L0, L1, L2）作为现有节点的下一个节点
    • 当索引下标为2取余结果为偶数时，从栈取出节点（此处取出的依次是Ln, Ln-1, Ln-2）作为现有节点的下一个节点
  • 顺延当前节点至下一个next指针
  • 在遍历完链表长度后，当前节点便是最终链表的最后一个节点，此时需要该节点的next指针进行置空操作，防止形成循环链表

b. 双指针

  • 依赖列表的下标索引便捷性，遍历一次原始链表，将节点按下标顺序写入list列表变量
  • 生成左指针l和右指针r，依据上述得到的列表变量list，同时开启循环对该两处下标的节点进行next指针的变更
  • 在每次变更结束后，左指针l向右移动一个单位，右指针r向左移动一个单位，直至l >= r
  • 当上述循环结束后，对结尾指针的next指针进行置空操作，防止形成循环链表

3. 代码

a. 栈 & 队列

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
/**
 * 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) {
        Deque<ListNode> leftQueue = new ArrayDeque<>();
        Deque<ListNode> rightStack = new ArrayDeque<>();
        
        var i = 1;

        var node = head;
        while (node != null) {
            leftQueue.offer(node);
            rightStack.push(node);
            node = node.next;
            i++;
        }
        
        var length = i;
        var newNode = new ListNode(-1, null);
        for (i = 1; i < length; ++i) {
            if (i % 2 == 1) {
                newNode.next = leftQueue.poll();
            } else {
                newNode.next = rightStack.pop();
            }

            newNode = newNode.next;

            if (i + 1 == length) {
                newNode.next = null;
            }
        }
    }
}

b. 双指针

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
/**
 * 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) {
        List<ListNode> list = new ArrayList<>();

        ListNode node = head;

        while (node != null) {
            list.add(node);
            node = node.next;
        }

        var size = list.size();

        if (size > 1) {
            var l = 0;
            var r = size - 1;
            while (l < r) {
                list.get(l).next = list.get(r);
                list.get(r).next = list.get(l + 1);
                l++;
                r--;
            }
            if (l == r) {
                list.get(r).next = null;
            } else {
                list.get(r + 1).next = null;
            }
        }
    }
}

4. 复杂度

两种解法，相比来讲，个人认为栈 & 队列更加形象和便于记忆，但使用到的空间也会比双指针多一倍，空间复杂度实际上是O(2n)，双指针做法相对来讲则性能更高

a. 栈 & 队列

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230801003651159

b. 双指针

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230801003603843