LeetCode143-重排链表

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/reorder-list/

中文链接：https://leetcode-cn.com/problems/reorder-list/

题目详述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

1
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

1
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

题目详解

可以分为三个步骤进行：

  • 把链表从中间断开，分成前后两个链表。
  • 翻转后面那个链表。
  • 合并两个链表。

找到中间点可以使用快慢指针，也可以计算长度。

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
public class LeetCode_00143 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode s = slow.next;
        slow.next = null;           // 断链
        ListNode h = reverse(s);    // 翻转
        while (h != null) {         // 合并
            ListNode next = head.next;
            head.next = h;
            head = h;
            h = next;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}