LeetCode 143. Reorder List

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).

Leave a Reply

Your email address will not be published.