题目链接

143. 重排链表

题目描述

给定一个单链表 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]

示例 2：

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

解题思路

1. 中点 + 翻转 + 合并

class Solution {
    public void reorderList(ListNode head) {
        // 1. 双指针找中点断链
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode rHead = slow.next;
        slow.next = null;
        // 2. 翻转后半部分链表
        rHead = reverse(rHead);
        // 3. 前半部分链表与翻转后的链表合并
        while (rHead != null) {
            ListNode t1 = head.next;
            ListNode t2 = rHead.next;
            head.next = rHead;
            rHead.next = t1;
            head = t1;
            rHead = t2;
        }
    }
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}