Description
https://leetcode.com/problems/reorder-list/
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder 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
Explanation
Find the first half and second half of the node list. Keep the first half order, and reverse the second half node list. Then mix the nodes from the first half list and the second half list.
Python Solution
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
count = 0
current = head
while current != None:
current = current.next
count += 1
if count % 2 == 0:
mid = count // 2
else:
mid = (count + 1) // 2
first_half = []
second_half = []
current = head
index = 0
while current != None:
if index < mid:
first_half.append(current)
else:
second_half.append(current)
current = current.next
index += 1
second_half = list(reversed(second_half))
current = first_half.pop(0)
for i in range(count - 1):
if i % 2 == 0:
current.next = second_half.pop(0)
else:
current.next = first_half.pop(0)
current = current.next
current.next = None
- Time Complexity: O(N).
- Space Complexity: O(N).