本文共 1941 字，大约阅读时间需要 6 分钟。

题目地址：

给定一个链表，从表头开始编号依次为$0,1,2,3,...,n$，要求将其重排序，使得编号为$0,n,1,n-1,2,n-2,...$。

可以按照如下顺序操作：

代码如下：

public class Solution {       /**     * @param head: The head of linked list.     * @return: nothing     */    public void reorderList(ListNode head) {           // write your code here        if (head == null) {               return;        }        ListNode mid = findMid(head);        ListNode secondHalf = mid.next;        mid.next = null;                secondHalf = reverse(secondHalf);        merge(head, secondHalf);    }        private ListNode findMid(ListNode head) {           ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode slow = dummy, fast = dummy;        while (fast != null && fast.next != null) {               slow = slow.next;            fast = fast.next.next;        }                return slow;    }        private ListNode reverse(ListNode head) {           ListNode prev = null;        while (head != null) {               ListNode tmp = head.next;            head.next = prev;            prev = head;            head = tmp;        }                return prev;    }        private ListNode merge(ListNode l1, ListNode l2) {           ListNode dummy = new ListNode(0), prev = dummy;        boolean odd = true;        while (l1 != null || l2 != null) {           	// 由于已经知道了l1的长度或者和l2相等，或者大1，所以这里并不需要对l1或者l2判空            if (odd) {                   prev.next = l1;                l1 = l1.next;            } else {                   prev.next = l2;                l2 = l2.next;            }            prev = prev.next;            odd = !odd;        }                return dummy.next;    }}class ListNode {       int val;    ListNode next;    ListNode(int x) {           val = x;    }}

时间复杂度$O(n)$，空间$O(1)$。