Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
The description was taken from https://leetcode.com/problems/reorder-list/.
#O(N) Time, O(1) Spaceclass Solution: def reorderList(self, head: ListNode) -> None: if not head: return [] fast = slow = head while fast and fast.next: fast = fast.next.next slow = slow.next previous, current = None, slow
while current:
bridge = current.next
current.next = previous
previous = current
current = bridge first, second = head, previous while second.next: temp = first.next first.next = second first = temp temp = second.next second.next = first second = tempIf we are needing the linked list to be ordered with the first node, the last node, the second node, the second to last node, etc., all we need to do is solve this with a similar method as Palindrome Linked List.
We can reverse the second half of the list then have one pointer at the beginning and one at the end. We will then move the pointers inward and interweave the list nodes.
We will start by seeing if the linked list we've been given is empty, if that is the case then we can't reorder it.
if not head: return []
Next, we will get the middle node so we can reverse every node after it.
We will initialize our fast and slow pointers at the head of the linked list.
fast = slow = head
Then, we will traverse the list with our pointers. During each iteration, we will increment the slow pointer once and the fast pointer twice.
Once the fast pointer is at the end of the list, the slow pointer will be halfway to the end.
while fast and fast.next: fast = fast.next.next slow = slow.next
Once the slow pointer is at the midpoint, we will begin reversing the second half of the list.
We will do this by utilizing three pointers. Our previous pointer will be used to track the previous node, current will be used to track the current node, and bridge will be used to track the next node.
We will initialize our previous and current pointers, with the current pointer being where slow was. The node the slow pointer is at will be the head of its sublist once reversed.
previous, current = None, slow
While the second pointer isn't at a null node, we continue moving down the list.
At the beginning of each iteration, we will save pointer_three as the next node.
pointer_three = pointer_two.next
While the current pointer isn't at a null node, we continue moving down the list, setting each current pointer's next reference to the previous node.
while current:
At the beginning of each iteration, we will save bridge as the next node.
bridge = current.next
We want to do this because once we overwrite current.next and set it to the previous node, we will lose our bridge to get to the next node.
Once we saved our bridge, we will overwrite the reference to our next node by setting it to the previous node, previous.
current.next = previous
We will then move our previous pointer to the current pointer, and our current pointer will cross the bridge to the next node.
previous = current
current = bridge
Once we have broke from the loop, that means that the current is now at the null node, so the previous pointer is at the head of the right sublist.
We'll set two more pointers for our interweaving. The first pointer will go to the head of the left sublist and the second will go to the head of the right sublist.
first, second = head, previous
Once we have reversed the node pointers, our list partitions will go from this:
head1->2->3->4->5->6->None
to this:
head 1->2->3->4->None
previous 6->5->4->None
We can now start interweaving the lists.
while second.next:
We will save the first pointer's node's reference to the next node to a temporary variable so that we don't lose the reference after we overwrite the next node.
We will then set the first pointer's next node to the second pointer's node.
Then, we will iterate to the node we saved in the temporary variable.
temp = first.next first.next = second first = temp
We will do the same thing but with the second pointer moving to the first pointer.
temp = second.next second.next = first second = temp
The interweaving will look like this:
first 1->2->3->4->None
| / | / | /
second 6->5->4->None
The final list will be:
head1->6->2->5->3->4->None