NC2题解 | #重排链表#

两种方式：

• 双端队列
• 快慢指针

1. 双端队列

	public static void reorderList1(ListNode head) {
        if(head == null){
            return;
        }
        LinkedList<ListNode> list = new LinkedList();
        ListNode cur = head;
        while(cur!=null){
            list.add(cur);
            cur=cur.next;
        }
        int count = list.size();
        int index =0;
        boolean flag = false;//默认是偶数
        if(count%2 == 0){
            index = count/2;
        }else{
            index = count/2+1;
            flag = true;
        }
        ListNode res = new ListNode(0);
        for(int i = 1; i <= index; i++){
            if(i<index){
                res.next = list.pollFirst();
                res = res.next;
                res.next = list.pollLast();
                res = res.next;
            }else{
                //奇数
                if(flag){
                    res.next = list.poll();
                    res = res.next;
                    res.next = null;
                }else{
                    res.next = list.pollFirst();
                    res = res.next;
                    res.next = list.pollLast();
                    res = res.next;
                    res.next = null;
                }
            }
        }
    }
 

2. 快慢指针

public static void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        ListNode res = new ListNode(0);
        ListNode p = head;
        //链表反转
        ListNode q = reverse(newHead);
        //链表合并
        while(p!=null && q!=null){
            res.next = p;
            res = p;
            p = p.next;
            res.next = q;
            res = q;
            q = q.next;
        }
        //快慢指针的特性注定了p的节点数一定是等于q或者比q多一个
        while(p!=null){
            res.next = p;
            res = res.next;
            p = p.next;
        }
    }
    public static ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = null;
        while(pre != null){
            ListNode temp = pre.next;//暂存
            pre.next = cur;
            cur = pre; //顺序不能反
            pre = temp;
        }
        return cur;
    }