# LeetCode Exercises for Python Linked List

## Python Singly Linked List Problems on LeetCode

Here are some LeetCode practice problems I believe will help you with interviews as well.

Merge two sorted linked list

You are given two linked list, list1 = [1,2,6], list2 = [5,1,3]

o/p : [1,1,2,3,5,6]

`class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def mergeTwoLists(self, l1, l2): """ :type list1: Optional[ListNode] :type list2: Optional[ListNode] :rtype: Optional[ListNode] """ prehead = ListNode(-1) temp = prehead while l1 and l2: if l1.val <= l2.val: temp.next = l1 l1 = temp.next else: temp.next = l2 l2 = temp.next temp = temp.next temp.next = l1 if l1 not none else l2 return prehead.next`

*Explanation :*`prehead = ListNode(-1)`

: This is a dummy node. The merged linked list will start from here.`temp = prehead`

: We are assigning a temporary pointer node to traverse. It is initially pointed to`prehead`

.`while l1 and l2`

: This loop will continue as long as there are no nodes left behind to compare.`if l1.value <= l2.value`

: This condition compares the current value of`l1`

and`l2`

`temp.next = l1`

and`l1 = temp.next`

: if the value of current node in`l1`

is equal or less than the current value of`l2`

, then we add the current node of`l1`

into the new list and we move forward in`l1`

`else`

: if the current value of`l1`

is greater than`l2`

.`temp = temp.next`

: after adding all the nodes, we need to move forward in the merged list too.`temp.next = l1 if l1 not none else l2`

: after traversing one of the list should be`none`

. So the non-none list should be merged to the new list`return prehead.next`

: this is a dummy node. The merged, sorted linked list starts after`prehead.next`

.*Time and Space Complexity:*`class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next`

Time Complexity: O(1); Initializing takes constant time.

Space Complexity: O(1); A single node's memory allocation is cons.

`def mergeTwoLists(self, l1, l2):`

Time Complexity: O(1) - Function definition does not involve any computation.

Space Complexity: O(1) - No extra space is being used here.

`prehead = ListNode(-1)`

Time Complexity: O(1) - Creating a single node takes cons time

Space Complexity: O(1) - Only one node creation takes cons space

`temp = prehead`

Time Complexity: O(1) - Assigning variable takes cons time

Space Complexity: O(1) - No space is being used here

`while l1 and l2: if l1.val <= l2.val: temp.next = l1 l1 = temp.next else: temp.next = l2 l2 = temp.next`

Time Complexity: O(m + n) - In the worst case scenerio, we have to iterate through both

`l1`

and`l2`

Space Complexity: O(1) - No space is being used here with the grow of new list. We are just using only a few pointers.

`temp.next = l1 if l1 not none else l2`

Time Complexity: O(1) - Assigning reference takes cons time

Space Complexity: O(1) - No additional space is being used here.

`return prehead.next`

Time Complexity: O(1) - Returning takes cons time operation

Space Complexity: O(1) - No additional space is being used here.

Remove duplicates

A sorted linked list's head is given. Delete all the duplicate values. Return the list on sorted from.

`class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def deleteDuplicates(self, head): #todo if not head: return None seen = set() dummy = ListNode(-1) dummy.next = head prev_node = dummy current_node = head while current_node: if current_node.val in seen: prev_node.next = current_node.next current_node = current_node.next else: seen.add(current_node.val) prev_node = current_node current_node = current_node.next return dummy.next #Input: head = [1,1,2] #Output: [1,2]`

*Explanation:*`class Solution(object)`

: this defines a class named`Solution`

`def DeleteDuplicates(self, head)`

: This defines a method inside the`Solution`

class which aims to remove duplicate values.Inside the

`deleteDuplicates`

method:`if note head: return None`

: This checks if the head of the linked list is`None`

(i.e. empty linked list). If the list is empty, it returns`None`

.`seen = set()`

: This will create a list to store values that has been already seen in the given linked list`dummy = ListNode(-1)`

: Creates a dummy node with a value of -1. This is a common technique to simplify edge cases, specailly the beginning of the linked list`dummy.next = head`

: This links the dummy node with the to the start of the linked list`prev_node = dummy`

: This assigns the`prev_node`

variable to the dummy node. It is used to keep track of the previous node while iterating.`current_node = head`

: This initializes the`current_node`

variable to the head of the linked list, i.e., the first node.`while if`

: It checks each nodes of the linked list. It checks if the nodes has been seen n=before, i.e. duplicate,i.

`prev_node.next = current_node.next`

: If it's a duplicate, this line skips the current node by connecting the previous node to the next node of the current one.ii.

`current_node = current_node.next`

: This moves the current node pointer to the next node in the list.`else`

: if the value of the current node has not been seen before:i.

`seen.add(current_node.val)`

: This adds the value of the current node to the`seen`

set.ii.

`prev_node = current_node`

: This updates the`prev_node`

to be the current node.iii.

`current_node = current_node.next`

: This moves the current node pointer to the next node in the list.return dummy.next : This returns the linked list starting from the node next to the dummy.

*Time and Space Complexity:*

`if not head: return None`

**Time Complexity**: O(1) (Constant time operation checking if head exists.)**Space Complexity**: O(1) (No additional space is being used.)

`seen = set()`

**Time Complexity**: O(1) (Initializing an empty set.)**Space Complexity**: O(n) in the worst case (if all elements are unique in the linked list, where n is the number of nodes.)

`dummy = ListNode(-1)`

**Time Complexity**: O(1) (Creating a single node.)**Space Complexity**: O(1)

`dummy_next = head`

**Time Complexity**: O(1)**Space Complexity**: O(1)

`prev_node = dummy`

**Time Complexity**: O(1)**Space Complexity**: O(1)

`current_node = head`

**Time Complexity**: O(1)**Space Complexity**: O(1)

`while current_node:`

**Time Complexity**: O(n) in total for the entire loop (as we iterate through each node of the linked list once.)**Space Complexity**: O(1) for the loop control itself, but the operations inside the loop might use additional space.`if current_node.val in seen:`

-**Time Complexity**: O(1) on average for set lookup, but in the worst case, it can be O(n). -**Space Complexity**: O(1)`else:`

i.`seen.add(current_node.val)`

-**Time Complexity**: O(1) on average for adding an item to a set, but in the worst case, it can be O(n). -**Space Complexity**: O(1) for the current operation but considering the set's size, it can be O(n) in total for all unique items.

`return dummy_next`

**Time Complexity**: O(1)**Space Complexity**: O(1)

*Final Complexity Analysis:*

**Total Time Complexity**: O(n) primarily because of the loop that goes through all the nodes. The set operations (lookup, insertion) are usually O(1) on average, but in the worst-case scenario, they could be O(n). However, since we're iterating through the list just once, the dominant factor remains O(n).**Total Space Complexity**: O(n) because of the`seen`

set which in the worst case might store all unique values from the linked list. The other operations and variables combined don't exceed this space complexity.

Remove linked list elements

Given the

`head`

of a linked list and an integer`val`

, remove all nodes where`Node.val == val`

and return*the new head*.`class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def removeElements(self, head, val): dummy_head = ListNode(-1) dummy_head.next = head prev_node, current_node = dummy_head, head while current_node: if current_node.val == val: prev_node.next = current_node.next else: prev_node = current_node current_node = current_node.next return dummy_head.next #Input: head = [1,2,6,3,4,5,6], val = 6 #Output: [1,2,3,4,5]`

none type object has no next, that's why using

`current_node`

instead of`head`

.*Explanation:*`def removeElements(self, head, val):`

This line starts the definition of our solution method, which takes a head of a linked list and a value to remove from the list.

`dummy_head = ListNode(-1)`

Creating a dummy head node. This node acts as a placeholder and helps handle cases where we need to remove the actual head of the list.

`while current_node:`

This line starts a loop that will continue as long as 'current_node' is not None, i.e., until we've checked every node in the list.

`if current_node.val == val:`

This line checks if the value of the current node is the value we want to remove.

`prev_node.next = current_node.next`

If the current node's value is the value we want to remove, this line skips over the current node by setting the 'next' attribute of the previous node to the node after the current one.

`else: prev_node = currrent_node`

If the current node's value isn't the one we want to remove, this line moves the 'prev_node' pointer to the current node.

`current_node = current_node.next`

This line moves the 'current_node' pointer to the next node in the list, regardless of whether we removed the current node or not.

*Time and Space Complexity:*

The while loops conducts an O(n) time complexity. So, the overall Time complexity is O(n) time complexity and as no extra space is being used here, the overall space complexity is O(1)

Reverse linked list

A singly linked list, head is given. Reverse the head and return the reversed linked list.

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

Input: head = []

Output: []

```
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def reverseList(self, head):
# Solution goes here
prev_node = None
curr_node = head
while curr_node is not None:
next_node = curr_node.next
curr_node.next = prev_node
prev_node = curr_node
curr_node = next_node
return prev_node
```

*Explanation:*

`prev_node = None`

This line initializes a variable

`prev_node`

to`None`

. This variable will be used to keep track of the previous node as we traverse the linked list.`curr_node = head`

This line initializes another variable

`curr_node`

to the`head`

of the linked list. This variable will be used to traverse the linked list.`while curr_node is not None:`

This line starts a

`while`

loop that will continue until`curr_node`

is`None`

. This is essentially saying "keep going until we've visited every node in the linked list".`next_node = curr_node.next`

Inside the while loop, this line saves the next node of

`curr_node`

before changing the next of`curr_node`

. This is crucial because once we reverse`curr_node.next`

, we lose the reference to the next node in the original list.`curr_node.next = prev_node`

This line reverses the direction of the link between the current and the previous node. Instead of

`curr_node`

pointing to the next node in the original list, it now points back to the node before it.`prev_node = curr_node`

This line shifts

`prev_node`

one step forward (to the right in the original list). Now,`prev_node`

is the`curr_node`

.`curr_node = next_node`

This line also shifts

`curr_node`

one step forward. However, this uses`next_node`

, which we saved before, to move`curr_node`

to its original next node in the list.`return prev_node`

After the while loop has completed, which means we have traversed and reversed all nodes in the list,

`curr_node`

is`None`

(as this condition breaks the while loop) and`prev_node`

is at the last node visited, which is the head of the reversed list. So, we return`prev_node`

.

*Time and Space Complexity:*

In summary, each line inside the loop has a time complexity of O(n), and the loop runs n times. Thus, the overall time complexity is O(n). Since no extra space is required here, the space complexity is O(1)

Palindrome linked list

`head`

of a singly linked list is given, return`true`

*if it is a palindrome or*`false`

*otherwise*.Input: head = [1,3,3,1]

Output: true

and,

Input: head = [1,2]

Output: false

```
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def isPalindrome(self, head):
#TODO
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
while prev:
if head.val != prev.val:
return False
head = head.next
prev = prev.next
return True
```

*Explanation:*

`slow = fast = head`

Here we're setting both

`slow`

and`fast`

to start at the head of the linked list. These are pointers that will be used to traverse the linked list.`while fast and fast.next:`

This line begins a loop that will continue until the

`fast`

pointer reaches the end of the list. The`fast`

pointer moves twice as fast as the`slow`

pointer. So, by the time`fast`

reaches the end,`slow`

will be at the midpoint of the list.`slow = slow.next`

and`fast = fast.next.next`

Inside the loop, we're moving

`slow`

one step forward and`fast`

two steps forward in each iteration. This is how we ensure`slow`

is at the midpoint when`fast`

reaches the end.`prev = None`

We're initializing

`prev`

to`None`

before starting to reverse the second half of the linked list.`while slow:`

This loop will reverse the second half of the linked list. It continues until all nodes in the second half are visited.

`nxt = slow.next`

Here we're saving the next node of

`slow`

before changing its reference.`slow.next = prev`

This line is making the

`slow`

node point back to the previous node, which is the essence of reversing the list.`prev = slow`

and`slow = nxt`

Here, we're moving

`prev`

one step forward and then moving`slow`

to its next node (saved in`nxt`

).`while prev:`

This loop will continue as long as there are nodes in the reversed list (

`prev`

).`if head.val != prev.val: return False`

Inside this loop, we're comparing the node values of the first half and the second half (reversed). If any pair of nodes have different values, we return

`False`

, implying the list is not a palindrome.`head = head.next`

and`prev = prev.next`

We're moving the pointers of the original list (

`head`

) and reversed list (`prev`

) one step forward for the next comparison in each iteration.`return True`

If the control reaches this line, it means all pairs of nodes have been checked and none have mismatched. Hence, we return

`True`

because the linked list is a palindrome.

*Space and Time complexity:*

In total, the time complexity is O(n) because each operation involving n is linear and while loop being an O(n) time complexity took the lead. The space complexity is O(1) as no extra space is required.

Middle of the linked list

Given the

`head`

of a singly linked list, return*the middle node of the linked list*.If there are two middle nodes, return

**the second middle**node.Input: head = [1,2,3,4,5]

Output: 3

Explanation: The middle node of the list is node 3.

```
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def middleNode(self, head):
fast = head
while fast and fast.next:
head = head.next
fast = fast.next.next
return head
```

*Explanation:*

`class Solution(object):`

We're declaring a new class named`Solution`

. In Python, we usually encapsulate related functions and variables inside a class.`def middleNode(self, head):`

We're defining a method called`middleNode`

inside the`Solution`

class. This method takes two parameters:`self`

, which is a reference to the current instance of the class, and`head`

, which is the head of the linked list.`fast = head`

Here, we're initializing a variable called`fast`

and setting it equal to`head`

. This variable will serve as one of our pointers that will traverse through the linked list.`while fast and fast.next:`

This begins a while loop that will continue until`fast`

is`None`

(which would mean we've reached the end of the list) or`fast.next`

is`None`

(which would mean we're at the second to last node).`head = head.next`

Within the loop, we're moving`head`

one step forward in the list.`fast = fast.next.next`

Then, we're moving`fast`

two steps forward. This line also implicitly checks whether`fast.next`

is`None`

, since Python will raise an exception if we try to access`None.next`

.`return head`

Once the loop ends,`head`

is now at the middle node of the list, so we return`head`

.

The purpose of this method is to find and return the middle node of a linked list. We do this by moving `fast`

twice as fast as `head`

. By the time `fast`

reaches the end of the list, `head`

will be at the middle.

*Space and Time Complexity:*

Overall, the time complexity of this function is O(n) because we're traversing the list once. The space complexity is O(1) because we're only using a fixed amount of space that does not grow with the size of the input list.

Be sure to practice them. Don't worry if you are a slow learner and don't get panicked if it's taking you couple of hours to understand and write one code. Don't be sad if finishing them takes more than one day or couple of day. Chill, we are just learners.

In the next blog, I will be talking about **Circular Singly Linked List**.

Stay Hydrated!