题目描述

给定一个单链表 $L：L_0→L_1→…→$$L_{n-1}$$→L_n$ ，
将其重新排列后变为：$ L_0→L_n→L_1→$$L_{n-1}$$→L_2→$$L_{n-2}$$→…$

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

样例

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

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

算法分析

• 1、使用快慢指针,找出链表的中心节点，分成两个链表

• 2、将右边的链表进行反转

• 3、合并两个链表

时间复杂度 $O(n)$

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head)
    {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverse(ListNode head)
    {
        if(head == null || head.next == null) return head;
        ListNode tail = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
    public ListNode merge(ListNode left,ListNode right)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        while(left != null && right != null)
        {
            t.next = left;
            t = t.next;
            left = left.next;

            t.next = right;
            t = t.next;
            right = right.next;
        }
        if(left != null) {t.next = left ; t = t.next; left = left.next;}
        if(right != null) {t.next = right ; t = t.next; right = right.next;}
        return dummy.next;
    }
    public void reorderList(ListNode head) {
        if(head == null) return ;

        ListNode middle = middleNode(head);

        ListNode left = head;
        ListNode right = reverse(middle.next);
        middle.next = null;

        head = merge(left,right);
    }
}