Java版LeetCode

Appearance

LCR 026. 重排链表 ​

题目 ​

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

L0→ L1→ ... → Ln-1→ Ln

请将其重新排列后变为：

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

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

示例 1:

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

示例 2:

输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
输入: 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/

题解 ​

java
public void reorderList(ListNode head) {
    // 使用快慢指针找链表中点
    ListNode slow = new ListNode(0, head), fast = new ListNode(0, head);
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 待倒叙的链表
    ListNode mid = slow.next;
    // 顺序链表后置空
    slow.next = null;
    ListNode reverse = new ListNode(0), t;
    // 将后半部分链表倒置
    while (mid != null) {
        t = mid.next;
        mid.next = reverse.next;
        reverse.next = mid;
        mid = t;
    }

    // 根据题意 顺序链表肯定长度大于(节点数位奇数的时候大于)等于倒叙链表
    reverse = reverse.next;
    // 交叉合并两个链表
    while (reverse != null) {
        t = head.next;
        head.next = reverse;
        reverse = reverse.next;
        head.next.next = t;
        head = t;
    }
}
public void reorderList(ListNode head) {
    // 使用快慢指针找链表中点
    ListNode slow = new ListNode(0, head), fast = new ListNode(0, head);
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 待倒叙的链表
    ListNode mid = slow.next;
    // 顺序链表后置空
    slow.next = null;
    ListNode reverse = new ListNode(0), t;
    // 将后半部分链表倒置
    while (mid != null) {
        t = mid.next;
        mid.next = reverse.next;
        reverse.next = mid;
        mid = t;
    }

    // 根据题意 顺序链表肯定长度大于(节点数位奇数的时候大于)等于倒叙链表
    reverse = reverse.next;
    // 交叉合并两个链表
    while (reverse != null) {
        t = head.next;
        head.next = reverse;
        reverse = reverse.next;
        head.next.next = t;
        head = t;
    }
}