题解 | #重排链表#

/*
	步骤：1、用快慢指针找到后一半链表的头结点；
          2、反转后一半链表；
          3、交叉得合并两个链表；
*/
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return;
        ListNode l1 = head;
        ListNode l2 = reverse(getMidNode(head));
        head = crossMerge(l1, l2);
    }
    public static ListNode getMidNode(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        return mid;
    }
    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    public static ListNode crossMerge(ListNode l1, ListNode l2){
        ListNode head = l1;
        ListNode temp = null;
        while(l2 != null){
            temp = l2.next;
            l2.next = l1.next;
            l1.next = l2;
            l1 = l2.next;
            l2 = temp;
        }
        return head;
    }
}