题解 | #重排链表#

普通做法：用一个数组集合保存下来，然后按需遍历。

public class Solution {
    public void reorderList(ListNode head) {
        if(head==null) return;
//         初级：使用集合存储然后按需遍历
        List<ListNode> res = new ArrayList<>();
        ListNode node = head;
        while(node!=null){
            res.add(node);
            node = node.next;
        }
//         按需遍历，在原链表上修改
        int i = 0,j = res.size()-1;
        while(i<j){
            res.get(i).next = res.get(j);
            i++;
            if(i==j) break;
            res.get(j).next = res.get(i);
            j--;
        }
        res.get(i).next = null;
    }
}

进阶：不适用外部空间，找到中间节点截断；然后将后半部分翻转；最后两部分直接映射

public class Solution {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null) return;
        // 找到中间节点
        ListNode mid = middle(head);
        // 后半部分节点位置
        ListNode l2 = reverse(mid.next);
        ListNode l1 = head;
        // 截取了
        mid.next = null;
        mapping(l1,l2);
    }
    // 考点：如何找到一个链表的中间节点？双指针
    public ListNode middle(ListNode head){
        ListNode slow = head,fast=head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    // 考点：翻转链表，这里用递归的形式
    public ListNode reverse(ListNode node){
        if(node.next == null || node==null) return node;
        ListNode pre = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return pre;
    }
    public void mapping(ListNode l1,ListNode l2){
        // 保留后一个节点
        ListNode l1Temp=null,l2Temp=null;
        while(l1!=null && l2!=null){
            l1Temp = l1.next;
            l2Temp = l2.next;
            l1.next = l2;
            l1 = l1Temp;
            l2.next = l1;
            l2 = l2Temp;
        }
    }
}