[LeetCode] Reorder List

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}.

Solution: First we count the total number of elements in the linked list, and we reverse the second half. In the end, we merge these two lists.

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

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode h = reverseList(head.next); head.next = null; ListNode p = h; while (p.next != null) { p = p.next; } p.next = head; return h; } public void reorderList(ListNode head) { int num = 0; ListNode p = head; while (p != null) { num++; p = p.next; } if (num <= 2) return; int mid = (num + 1) / 2; p = head; while (mid > 1) { mid--; p = p.next; } ListNode h = reverseList(p.next); p.next = null; p = head; ListNode q = h; while (p != null && q != null) { ListNode r = q.next; q.next = p.next; p.next = q; p = q.next; q = r; } return; } }