143. Reorder List 发表于 2022-01-18 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { public void reorderList(ListNode head) { // d -> 1 -> 2 -> 3 -> 4 // f // s // d -> 1 -> 2 -> 3 -> 4 -> 5 // f // s ListNode dummyHead = new ListNode(-1, head); ListNode fast = dummyHead, slow = dummyHead; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode rightHead = slow.next; slow.next = null; ListNode reversedRightHead = reverse(rightHead); ListNode nodeB = reversedRightHead, nodeA = head; while (nodeB != null) { ListNode nextA = nodeA.next; nodeA.next = nodeB; ListNode nextB = nodeB.next; nodeB.next = nextA; nodeA = nextA; nodeB = nextB; } } private ListNode reverse(ListNode node) { ListNode pre = null; while (node != null) { ListNode next = node.next; node.next = pre; pre = node; node = next; } return pre; }} Reference143. Reorder List剑指 Offer II 026. 重排链表