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:
1. /*
2. * Definition for singly-linked list.
3. * class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode(int x) {
7. * val = x;
8. * next = null;
9. * }
10. * }
11. /
12. public class Solution {
13. public void reorderList(ListNode head) {
14. if (head == null || head.next == null)
15. return;
16. 17. // step 1. cut the list to two halves
18. // prev will be the tail of 1st half
19. // slow will be the head of 2nd half
20. ListNode prev = null, slow = head, fast = head, l1 = head;
21. 22. while (fast != null && fast.next != null) {
23. prev = slow;
24. slow = slow.next;
25. fast = fast.next.next;
26. }
27. 28. prev.next = null;
29. 30. // step 2. reverse the 2nd half
31. ListNode l2 = reverse(slow);
32. 33. // step 3. merge the two halves
34. merge(l1, l2);
35. }
36. 37. ListNode reverse(ListNode head) {
38. ListNode prev = null, curr = head, next = null;
39. 40. while (curr != null) {
41. next = curr.next;
42. curr.next = prev;
43. prev = curr;
44. curr = next;
45. }
46. 47. return prev;
48. }
49. 50. void merge(ListNode l1, ListNode l2) {
51. while (l1 != null) {
52. ListNode n1 = l1.next, n2 = l2.next;
53. l1.next = l2;
54. 55. if (n1 == null)
56. break;
57. 58. l2.next = n1;
59. l1 = n1;
60. l2 = n2;
61. }
62. }
63. }