LCR 026. 重排链表(中等)

Posted on Edited on In Views:

1，题目描述

LCR 026. 重排链表

难度：中等

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

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

注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/

2，初步思考

方法1:空间换时间

​ 因为没有空间复杂度的限制，所以我们直接使用空间换时间

​ 将所有节点直接存储到hashMap中，后续直接按需取出排序即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void reorderList1(ListNode head) {
    HashMap<Integer, ListNode> map = new HashMap<>();
    ListNode pre = head;
    int counter = 0;
    // 缓存节点索引信息
    while (pre != null) {
        map.put(counter, pre);
        pre = pre.next;
        counter++;
    }
    // 直接按需重新排序
    for (int i = 0; i < ((counter - 1) / 2); i++) {
        ListNode listNode0 = map.get(i);
        ListNode listNode1 = map.get(i + 1);
        ListNode listNodeNdiffOne = map.get(counter - i - 2);
        ListNode listNodeN = map.get(counter - i - 1);
        listNode0.next = listNodeN;
        listNodeN.next = listNode1;
        listNodeNdiffOne.next = null;
    }
}

方法2:取中心、逆序、重拍

​ 截取到中心点，拆分成2条链，后面的链表逆序，之后再重新排列

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
public static void reorderList(ListNode head) {
    // 1，找到中间节点
    // 1234，4个，（n/2）+1=3
    // 12345,5个，（n/2）+1=3
    int counter = 1;
    ListNode pre = head;
    ListNode midle = head;
    while (pre.next != null) {
        counter++;
        pre = pre.next;
        if (counter % 2 == 0) {
            midle = midle.next;
        }
    }

    // 2，翻转后半部分链表
    // 一半的长度为 （n/2）+n%2
    ListNode newMidle = reverseListNode(midle);

    // 3，组合
    // 1,2,3,4
    // 1,2,3 4,3
    // 1,4,2 2,3 3
    //
    // 1,4,2,3
    pre = head;
    for (int i = 0; i < (counter / 2); i++) {
        ListNode ch = pre;
        ListNode cm = newMidle;

        pre = pre.next;
        newMidle = newMidle.next;

        ch.next = cm;
        if (cm.next != null) {
            cm.next = pre;
        }
    }
}

// 1,2,3,4
// 递归逆序
static ListNode reverseListNode(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseListNode(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}