143.重排链表

题目描述

题解

快慢指针 + 反转链表

先通过快慢指针的方法找出链表的中间节点, 以此为边界把后半段链表反转, 然后交错插入前半段链表中

public class lc143 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode head2 = reverse(slow.next);
        slow.next = null;

        ListNode pre = head;
        ListNode cur;
        ListNode cur2;

        while (head2 != null) {
            cur = pre.next;
            cur2 = head2.next;

            head2.next = pre.next;
            pre.next = head2;

            pre = cur;
            head2 = cur2;
        }

        System.out.println(head);
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;

        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }

        return pre;
    }
}