143. Reorder List — LeetCode(Python)
I got you!
Problem:
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → LnReorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]Constraints:
- The number of nodes in the list is in the range
[1, 5 * 104]. 1 <= Node.val <= 1000
Solution:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow
first = head
curr, prev = mid, None
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
second = prev
while second.next:
temp1 = first.next
first.next = second
first = temp1
temp2 = second.next
second.next = first
second = temp2Explanation —
We use two pointers here, a slow and a fast one, where the fast pointer is twice as fast as the slow one.
We iterate through the linked list until the fast pointer reaches the end of the list. This is when our slow pointer would be at the middle of the linked list.
We then reverse the 2nd half of the linked list.
Next, we link every element of the first half of the list with the corresponding element in the second half, shifting pointer at each step
Nothing is returned as the changes are made in place.
Time and Space Complexity —
Since we are iterating over the list in a linear way, though twice, we can say that our algorithm runs in linear time.
Also, we require a constant amount of extra space.
Thus, if n is the length of the linked list,
Time Complexity: O(n)
Space Complexity: O(1)
