Python Linked List LeetCode Practice

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.
1. Input: head = [1,2,3,4,5]
  
  Output: [5,4,3,2,1]
2. 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.
1. Input: head = [1,3,3,1]
  
  Output: true
  
  and,
2. 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.
1. Input: head = [1,2,3,4,5]
  
  Output: 3
2. 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!

LeetCode Exercises for Python Linked List

Python Singly Linked List Problems on LeetCode

Final Complexity Analysis: