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. Break list into two halves (use fast & slow pointers to find the middle node).
2. Reverse the second half.
3. Merge the two halves back together.
/**
* 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 || head.next == null) return;
// Find the middle of the list.
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
// Terminate the first half of the list.
slow.next = null;
// Reverse the second half of the list.
ListNode prev = null;
ListNode curr = mid;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Merge the two halves together.
ListNode first = head;
ListNode second = prev;
while (first != null && second != null) {
if (first != null) {
ListNode temp = first.next;
first.next = second;
first = temp;
}
if (second != null) {
ListNode temp = second.next;
second.next = first;
second = temp;
}
}
}
}
No comments:
Post a Comment