mediumLinked ListPattern: Simulation
Insert Interval into Sorted Linked List Solution
Problem Statement
You are given the head of a sorted linked list, where each node contains an integer value. You are also given a new interval represented by a start value and an end value. Insert a new node with the given start value into the linked list such that the list remains sorted. If a node with the same value already exists, do not insert the new node. Return the head of the modified linked list.
Examples
Example 1:
Input:head = [1, 3, 5, 7], newInterval = [4, 4]
Output:[1, 3, 4, 5, 7]
Explanation: The new node with value 4 should be inserted between 3 and 5 to maintain the sorted order.
Example 2:
Input:head = [2, 4, 6, 8], newInterval = [1, 1]
Output:[1, 2, 4, 6, 8]
Explanation: The new node with value 1 is inserted at the beginning as it's smaller than the current head.
Example 3:
Input:head = [1, 3, 5], newInterval = [3, 3]
Output:[1, 3, 5]
Explanation: A node with value 3 already exists, so no new node is inserted. The list remains unchanged.
Constraints
- The number of nodes in the list is in the range [0, 1000].
- Node values and new interval values are integers.
- The linked list is sorted in non-decreasing order.
- The new interval values will be positive.
- Node values will be positive.
Time: O(N) Space: O(1)
Traverse the linked list, keeping track of the previous node. Find the first node whose value is greater than or equal to the new interval's start value. If the value is not a duplicate, insert the new node before this node (or at the end if no such node is found). Handle the edge case of inserting into an empty list or at the head.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def insertInterval(self, head: Optional[ListNode], newInterval: list[int]) -> Optional[ListNode]:
val_to_insert = newInterval[0]
new_node = ListNode(val_to_insert)
if not head:
return new_node
current = head
prev = None
while current and current.val < val_to_insert:
prev = current
current = current.next
if current and current.val == val_to_insert:
return head # Value already exists
if prev is None:
# Insert at the beginning
new_node.next = head
return new_node
else:
# Insert in the middle or at the end
new_node.next = current
prev.next = new_node
return head