题解

先把链表对半分(快慢指针)

后半逆序

后半逐个间隔插入前半

/**
* 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) {
     if (head == null || head.next == null || head.next.next == null) {
         return ;
     }

     ListNode slow = head;
     ListNode fast = head;
     while (fast != null && fast.next != null) {
         slow = slow.next;
         fast = fast.next.next;
     }

     ListNode headList = head;
     ListNode tailList = slow.next;
     slow.next = null;

     tailList = reverse(tailList);
     insert(headList, tailList);
 }

 private ListNode reverse(ListNode head) {
     ListNode dummy = new ListNode(0);
     ListNode node = head;
     while (node != null) {
         ListNode nodeNext = node.next;
         node.next = dummy.next;
         dummy.next = node;
         node = nodeNext;
     }
     return dummy.next;
 }

 private void insert(ListNode listA, ListNode listB) {
     ListNode nodeA = listA;
     ListNode nodeB = listB;

     while (nodeB != null) {
         ListNode nodeANext = nodeA.next;
         ListNode nodeBNext = nodeB.next;

         nodeA.next = nodeB;
         nodeB.next = nodeANext;
         nodeA = nodeANext;
         nodeB = nodeBNext;
     }
 }
}