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 # ??