Linked Lists

11 Sep, 2024

Traversing a singly-linked list :

cur = ListNode1
while (cur!=NULL) :
	cur = cur.next

Time Complexity : O(N)

Adding a new node to the linked list :

LeetCode/NeetCode Practice Questions:

1. Merge two sorted linked lists:

intuition / approach :

a. you create a dummy node to avoid the edge cases of empty list

b. the other edge case is when we have finished iterating through one list but we are still left with elements from the other list -

in this case all we need to do is take the remaining elements from the list and add it to our output (lucky for me these lists were already sorted!)

so how do we go about creating a dummy node?

dummy = ListNode() # so that we dont have to worry about inserting into an empty list

note to future-self : have I figured out why dummy.next is returned?

solution :

dummy = ListNode() tail = dummy while list1 and list2: if list1.val < list2.val: tail.next = list1 list1 = list1.next # update the list1 pointer else: # list2.val <= list1.val tail.next = list2 list2 = list2.next #update the pointer tail = tail.next # but what if there is a portion of either list1 or list2 left which wasnt compared above if list1: tail.next = list1 if list2: tail.next = list2 return dummy.next # ??