Java关于重排链表详细解析

问题描述

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

L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln

需要将单链表 L 进行重新排列，使得新的链表既符合以下格式，也保留原链表元素的相对顺序：

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

例如，将单链表 L = 1 -> 2 -> 3 -> 4 -> 5 -> 6 进行重排后，新链表应为 1 -> 6 -> 2 -> 5 -> 3 -> 4 。

解题思路

初步看到这道题目，我们很容易想到的是：将单链表拆成前半段与后半段，然后将后半段翻转，最后将前半段与后半段交叉拼接。

将单链表拆成前半段与后半段

首先，我们需要找到单链表 L 的中间节点，可以使用快慢指针的方法，一个指针每次向后移动 1 个节点，另一个指针每次向后移动 2 个节点，当快指针到达链表末尾时，慢指针恰好到达中间位置，这样便可以将单链表拆分成前半段与后半段。

int length = 0;
ListNode node = head;
while (node != null) {
    length++;
    node = node.next;
}

ListNode node1 = head;
ListNode node2 = null;

for (int i = 0; i < (length + 1) / 2; i++) {
    node2 = node1;
    node1 = node1.next;
}

node2.next = null; // 将链表断成两半

翻转后半段链表

接下来，我们需要对后半段链表进行翻转。这个问题不难，只需要使用三个指针，分别指向当前节点、前驱节点和后继节点，然后对当前节点的 next 指针进行反转即可。

/**
 * 翻转链表
 * @param head
 */
public void reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;

    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

交叉拼接前半和后半段链表

最后，我们将前半段与翻转后的后半段依次交叉拼接即可。

ListNode cur1 = head;
ListNode cur2 = newHead;
ListNode next1 = null;
ListNode next2 = null;

while (cur2 != null) {
    next1 = cur1.next;
    next2 = cur2.next;

    cur1.next = cur2;
    cur2.next = next1;

    cur1 = next1;
    cur2 = next2;
}

完整代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 将链表断成两半
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }

        ListNode node1 = head;
        ListNode node2 = null;

        for (int i = 0; i < (length + 1) / 2; i++) {
            node2 = node1;
            node1 = node1.next;
        }

        node2.next = null;

        // 翻转链表
        ListNode pre = null;
        ListNode cur = node1;
        ListNode next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        ListNode newHead = pre;

        // 交叉拼接前半和后半段链表
        ListNode cur1 = head;
        ListNode cur2 = newHead;
        ListNode next1 = null;
        ListNode next2 = null;

        while (cur2 != null) {
            next1 = cur1.next;
            next2 = cur2.next;

            cur1.next = cur2;
            cur2.next = next1;

            cur1 = next1;
            cur2 = next2;
        }
    }
}

示例说明

示例 1

单链表 L = 1 -> 2 -> 3 -> 4 -> 5 -> 6

中间节点为 3 ，将单链表拆分成前半段 1 -> 2 -> 3 和后半段 4 -> 5 -> 6

翻转后半段链表，得到 6 -> 5 -> 4

交叉拼接前半段和后半段链表，得到 1 -> 6 -> 2 -> 5 -> 3 -> 4