Java-LeetCode143. 重排链表-分割链表&翻转链表

• 算法
  • 1.快慢指针找到中间节点
  • 2.可以看出找到的中间节点是一定挂在末尾不会变的，所以将其再移动一个位置，并且把它前面的节点挂个null表示前半部分链表结束
  • 3.翻转后半部分链表
  • 4.将翻转后的后半部分链表逐个插入前半部分即可

public void reorderList(ListNode head) {
    if (head == null) {
        return;
    }

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

    ListNode rightHalf = reverseList(slow);
    ListNode leftHalf = head;
    while (rightHalf != null) {
        ListNode leftNext = leftHalf.next;
        ListNode rightNext = rightHalf.next;

        leftHalf.next = rightHalf;
        rightHalf.next = leftNext;

        leftHalf = leftNext;
        rightHalf = rightNext;
    }
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}