题目连接

示例

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

解题思路

重排后为：第一个，倒数第一个，第二个，倒数第二个，第三个，倒数第三个。。。

整体思路就是：

• 首先，找到链表的中间节点，方法如上述的#876题；
• 接着，将链表的后半部分反转，放入如上述的#206题；
• 然后，将链表的前半部分和链表的后半部分反转后的结果进行合并。

代码

public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }
    // 获得中间节点
    ListNode mid = findMid(head);
    // 中间节点之后的部分进行反转
    ListNode head2 = mid.next;
    mid.next = null;
    head2 = reverseList(head2);
    // 合并
    ListNode head1 = head;
    mergeList(head1, head2);
}
// LeetCode 876
private ListNode findMid(ListNode head){
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast= fast.next.next;
    }
    return slow;
}
// LeetCode 206
private ListNode reverseList(ListNode head){
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode nextNode = cur.next;
        cur.next = prev;
        prev =cur;
        cur = nextNode;
    }
    return prev;
}
private void mergeList(ListNode head1, ListNode head2) {
    ListNode next1 = null;
    ListNode next2 = null;
    while (head1 != null && head2 != null) {
        next1 = head1.next;
        next2 = head2.next;
        head1.next = head2;
        head1 = next1;
        head2.next = head1;
        head2 = next2;
    }
}