Inserting a Node Into a Sorted Doubly Linked List| Linked List
TASK(easy)
Given a reference to the head of a doubly-linked list and an integer, , create a new DoublyLinkedListNode object having data value and insert it at the proper location to maintain the sort.
Function Description
Complete the sortedInsert function in the editor below.
sortedInsert has two parameters:
- DoublyLinkedListNode pointer head: a reference to the head of a doubly-linked list
- int data: An integer denoting the value of the data field for the DoublyLinkedListNode you must insert into the list.
Returns
- DoublyLinkedListNode pointer: a reference to the head of the list
Note: Recall that an empty list (i.e., where head=NULL) and a list with one element are sorted lists.
Input Format
The first line contains an integer t, the number of test cases.
Each of the test case is in the following format:
- The first line contains an integer n, the number of elements in the linked list.
- Each of the next n lines contains an integer, the data for each node of the linked list.
- The last line contains an integer, data, which needs to be inserted into the sorted doubly-linked list.
Constraints
1<=t<=10
1<=n<=1000
1<=DoublyLinkedListNode.data<=1000
Sample Input
STDIN Function
----- --------
1 t = 1
4 n = 4
1 node data values = 1, 3, 4, 10
3
4
10
5 data = 5
Sample Output
1 3 4 5 10
SOLUTION 1
def sortedInsert(llist, data):
head = llist
if llist.data > data: #board case
head = DoublyLinkedListNode(data)
head.next = llist
else:
while llist.next:
prev = llist
next_node = llist.next
if next_node.data > data:
new_node = DoublyLinkedListNode(data)
new_node.next = next_node
next_node.prev = new_node
prev.next = new_node
return head
llist = next_node
if llist.next == None: #board case
new_node = DoublyLinkedListNode(data)
new_node.prev = llist
llist.next = new_node
return head
SOLUTION 2
def sortedInsert(llist, data):
node = DoublyLinkedListNode(data)
if llist.data > data: # Pre-insert
node.next, llist.prev = llist, node
return node
head = llist
while head:
if not head.next: # Post-insert
head.next, node.prev = node, head
return llist
if head.next.data > data: # Mid-insert
head.next.prev, node.next = node, head.next
head.next, node.prev = node, head
return llist
head = head.next
return llist
EXPLANATION STEPS
1.Create New Node: Initialize the new node with the given value.
2.Handle Edge Cases: Check if the list is empty or if the new node should be inserted at the head.
3.Traverse List: Find the correct position for the new node.
4.Insert Node: Update pointers to insert the new node in the sorted order.
5.Update Head: If the new node is inserted at the head, update the head pointer.
