重排链表

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，143. Reorder List

先看题目描述

大意就是给定一个链表 : L0→L1→…→Ln-1→Ln，让我们将其重排为 L0→Ln→L1→Ln-1→L2→Ln-2…

算法和思路

双指针

这个是自己实现的算法，流程如下

算法流程：

  • 定义一个哈希表 map，将链表中的每个节点和其前序节点对应起来
  • 定义一个 first 指针和 last 指针分别指向链表的头节点和尾节点，通过 first 指针和 last 指针来遍历链表：
    • 将 last 对应节点插到 first 对应节点之后
    • first 指针向后移动两位
    • last 指针指向其之前的前序节点，并使其之前前序节点的 next 值为空
  • 重复上述操作直至 first 和 last 相遇或者 last 指向 first 指针的后一位

递归

如果我们的递归函数能够返回当前头元素对应的尾元素，并且将头元素和尾元素之间的链表按要求完成，那就变得简单了

BSdC9I.png

如上图，我们只需要将 head 指向 tail，tail 指向处理完的链表头即可

BSdKCn.png

然后我们把之前的 tail.next 返回就是外层 head 对应的 tail 了

递归出口的话，如果只有一个节点，那么我们只需要将 head.next 返回

如果是两个节点，我们需要将 head.next.next 返回

算法源码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        Map<ListNode, ListNode> map = new HashMap<ListNode, ListNode>();
        ListNode node = head;
        ListNode pre = null;
        while (node != null) {
            map.put(node, pre);
            pre = node;
            node = node.next;
        }
        ListNode first = head;
        ListNode last = pre;
        while (first != last && last != first.next) {
            last.next = first.next;
            first.next = last;
            last = map.get(last);
            last.next = null;
            first = first.next.next;
        }
    }
}

递归

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
class Solution {
    public void reorderList(ListNode head) {
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        if (len <= 2) return;
        reorder(head, len);
    }
    
    private ListNode reorder(ListNode head, int n) {
        if (n == 1) {
            ListNode node = head.next;
            head.next= null;
            return node;
        }
        if (n == 2) {
            ListNode node = head.next.next;
            head.next.next = null;
            return node;
        }
        ListNode tail = reorder(head.next, n - 2);
        ListNode node = tail.next;
        tail.next = head.next;
        head.next = tail;
        return node;
    }
}