题解 | #重排链表#

方法1:利用数组
方法2:利用快慢指针以及反转链表操作

import java.util.*;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    public void reorderList(ListNode head) {
//         method1(head);
        method2(head);
    }

    public void method1 (ListNode head) {

        if (head == null) {
            return;
        }

        ArrayList<ListNode> list = new ArrayList<>();

        while (head != null) {
            list.add(head);
            head = head.next;
        }

        int left = 0;
        int right = list.size() - 1;

        while (left < right) {
            list.get(left).next = list.get(right);
            left++;

            // 若 链表长度为偶数的情况下 则会提前相遇，此时已达到题目要求，直接终止循环
            if (left == right) {
                break;
            }

            list.get(right).next = list.get(left);
            right--;
        }

        list.get(left).next = null;
    }

    public void method2 (ListNode head) {

        if (head == null || head.next == null || head.next.next == null) {
            return;
        }

        ListNode slowNode = head;
        ListNode fastNode = head.next;

        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }

        //将后半段链表反转
        ListNode midNode = slowNode.next;
        slowNode.next = null;
        ListNode reverseNode = reverseNode(midNode);
        ListNode tempReverseNode = null;

        while (reverseNode != null) {
            tempReverseNode = reverseNode.next;
            reverseNode.next = head.next;
            head.next = reverseNode;
            head = reverseNode.next;
            reverseNode = tempReverseNode;
        }

    }

    public ListNode reverseNode (ListNode head) {

        ListNode curNode = head.next;
        ListNode preNode = head;
        ListNode tempNode = null;

        while (curNode != null) {
            tempNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = tempNode;
        }

        head.next = null;
        return preNode;
    }

}