LeetCode 143: Reorder List
Problem Description
Explanation
To reorder the linked list as required, we can follow these steps:
- Find the middle of the linked list using the slow and fast pointer technique.
- Reverse the second half of the list.
- Merge the first half with the reversed second half.
Time complexity: O(n)
Space complexity: O(1)
Solutions
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode middle = findMiddle(head);
ListNode secondHalf = reverseList(middle.next);
middle.next = null;
mergeLists(head, secondHalf);
}
private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private void mergeLists(ListNode l1, ListNode l2) {
while (l1 != null && l2 != null) {
ListNode l1Next = l1.next;
ListNode l2Next = l2.next;
l1.next = l2;
l2.next = l1Next;
l1 = l1Next;
l2 = l2Next;
}
}
}Related LeetCode Problems
Loading editor...