Good implementing question for LinkedList.
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode reverseHead = slow.next;
slow.next = null;
reverseHead = reverse(reverseHead);
ListNode curr = head;
while (reverseHead != null) {
ListNode temp = reverseHead.next;
reverseHead.next = curr.next;
curr.next = reverseHead;
curr = reverseHead.next;
reverseHead = temp;
}
}
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode prev = new ListNode(-1);
prev.next = head;
ListNode curr = head;
while (curr.next != null) {
ListNode temp = curr.next;
curr.next = temp.next;
temp.next = prev.next;
prev.next = temp;
}
return prev.next;
}
No comments:
Post a Comment