力扣 143 重排链表

题意：把链表重新排列

思路：见代码注释

思想：快慢指针

复杂度：时间O（n)，空间O(1)

class Solution {
    public void reorderList(ListNode head) {
        ListNode newhead = new ListNode(0);
        newhead.next = head;
        ListNode r1 = newhead;
        ListNode r2 = newhead;
        // 找到链表的后半部分节点的开始
        while(r1 != null && r1.next != null) {
            r1 = r1.next.next;
            r2 = r2.next;
        }
        ListNode temp = r2.next;
        r2.next = null;
        // 把后半部分节点倒转
        temp = reverse(temp);
        r1 = newhead.next;
        r2 = temp;
        // 把前半部分节点和后半部分节点重新组合
        while(r1 != null && r2 != null) {
            ListNode cur = r2;
            r2 = r2.next;
            cur.next = r1.next;
            r1.next = cur;
            r1 = r1.next.next;
        }
        newhead.next = null;
    }
    
    // 倒转链表
    ListNode reverse(ListNode node) {
        if(node == null)
            return node;
        ListNode newhead = new ListNode(0);
        newhead.next = node;
        ListNode run = node;
        while(run.next != null) {
            ListNode temp = run.next;
            run.next = run.next.next;
            temp.next = newhead.next;
            newhead.next = temp;
        }
        return newhead.next;
    }
}