题解 | #重排链表#

/**
 * 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) {
            return;
        }
        nodeChange(head, head.next);
        System.out.println(head);
    }
    private void nodeChange(ListNode pre, ListNode last) {
        if (last == null || last.next == null) {
            return;
        }
        ListNode temp = last;
        while (temp.next.next != null) {
            temp = temp.next;
        }

        pre.next = temp.next;
        pre.next.next = last;
        temp.next = null;
        nodeChange(pre.next.next, last.next);
    }
}

我的解法使用了递归变化，不知道是不是满足题目要求的使用原地算法