[LeetCode] 143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Thought process:

The idea is to split the list into two halves, reverse the second half, and merge them back together.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode middle = findMiddle(head); ListNode right = middle.next; middle.next = null; ListNode rightReversed = reverse(right); merge(head, rightReversed); } private ListNode findMiddle(ListNode head) { ListNode fast = head.next; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } private ListNode reverse(ListNode head) { ListNode previous = null; while (head != null) { ListNode next = head.next; head.next = previous; previous = head; head = next; } return previous; } private void merge(ListNode left, ListNode right) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (left != null && right != null) { current.next = left; left = left.next; current = current.next; current.next = right; right = right.next; current = current.next; } if (left != null) { current.next = left; } } }

Time complexity: O(n).