LeetCode-Reorder List

Description：
Given a singly linked list$L: L0→L1→…→Ln-1→Ln$L:L0→L1→…→Ln−1→Ln,
reorder it to: $L0→Ln→L1→Ln-1→L2→Ln-2→…$L0→Ln→L1→Ln−1→L2→Ln−2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

题意：给定一个链表$L: L0→L1→…→Ln-1→Ln$L:L0→L1→…→Ln−1→Ln，将其重新排序为$L0→Ln→L1→Ln-1→L2→Ln-2→…$L0→Ln→L1→Ln−1→L2→Ln−2→…

解法：从最后的排序结果来看可以分为两个部分，第一个部分是$L0→L1→L2→…$L0→L1→L2→…，第二个部分是$Ln→Ln-1→Ln-2→…$Ln→Ln−1→Ln−2→…；因此，通过将链表分为这两个部分后，再同时遍历合并链表即可；

1. 首先，找到右半部分链表的开始位置；
2. 将右半部分链表逆序；
3. 此时，同时从左半部分链表和有半部分链表开始遍历，合并链表

例如，对于链表1->2->3->4->5

第一步，找到右半部分链表的开始位置；
第二步，对右半部分执行逆序操作

第三步，合并左右两部分链表

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        
        //计算链表的长度
        ListNode p = head;
        int len = 0;
        while (p != null) {
            len++;
            p = p.next; 
        }
        
        //找到右半部分的开始位置
        ListNode left = head;
        ListNode right = head;
        p = head;
        for (int i = 0; i < (len+1)/2 - 1; i++) {
            p = p.next;
            right = right.next;
        }
        right = right.next;
        p.next = null;
        p = null;
        
        //将右半部分链表逆序
        while (right != null) {
            ListNode temp = right.next;
            right.next = p;
            p = right;
            right = temp;
        }
        right = p;
        
        //从左右两个链表头结点开始连接
        for (int i = 0; i < len/2; i++) {
            ListNode tempLeft = left.next;
            ListNode tempRight = right.next;
            left.next = right;
            right.next = tempLeft;
            left = tempLeft;
            right = tempRight;
        }
    }
}