题目描述

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

L0 → L1 → … → Ln – 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln – 1 → L2 → Ln – 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

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

题目分析

先找到中点，把链表拆分为2个，把后面的链表反转，最后再将2个链表合并。
空间复杂度 O(1)

Java

public void reorderList(ListNode head) {
    ListNode midNode = getMidNode(head);
    ListNode p1 = head, p2 = midNode.next;
    midNode.next = null;
    p2 = reverse(p2);
    merge(p1, p2);
}

private ListNode getMidNode(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

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

private void merge(ListNode p1, ListNode p2) {
    while (p1 != null && p2 != null) {
        ListNode next1 = p1.next;
        ListNode next2 = p2.next;
        p1.next = p2;
        if (next1 != null) {
            p2.next = next1;
        }
        p1 = next1;
        p2 = next2;
    }
}

Kotlin

fun reorderList(head: ListNode?): Unit {
    if (head == null) {
        return
    }
    val midNode = getMidNode(head)
    val p1 = head
    val p2 = reverse(midNode.next)
    midNode.next = null
    merge(p1, p2)
}

private fun getMidNode(head: ListNode): ListNode {
    var slow = head
    var fast = head.next
    while (fast?.next != null) {
        slow = slow.next!!
        fast = fast.next!!.next
    }
    return slow
}

private fun reverse(head: ListNode?): ListNode? {
    var pre: ListNode? = null
    var cur = head
    while (cur != null) {
        val temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
}

private fun merge(p1: ListNode?, p2: ListNode?) {
    var cur1 = p1
    var cur2 = p2
    while (cur1 != null && cur2 != null) {
        val next1 = cur1.next
        val next2 = cur2.next
        cur1.next = cur2
        if (next1 != null) {
            cur2.next = next1
        }
        cur1 = next1
        cur2 = next2
    }
}