Unlock the full potential of linked lists in this comprehensive post. Explore eleven powerful algorithms that will revolutionize the way you manipulate and operate on linked list data structures. Elevate your data structure and algorithms expertise with this transformative content. This post focuses on linked lists and demonstrates various operations that can be performed on linked lists using Python. A linked list is a fundamental data structure composed of nodes, where each node contains a value and a reference to the next node in the list. This notebook covers the basics of linked lists, including insertion, deletion, traversal, and searching operations. You can run this post in Google Colab using this link:

A linked list is a data structure that is commonly used in computer programming. It consists of a sequence of nodes, where each node contains a piece of data and a reference (or a “pointer”) to the next node in the sequence.

Linked lists are useful for representing sequences of data where the order of the data is important, but where the actual physical arrangement of the data in memory is not important. This is because linked lists can be easily modified to insert, delete or rearrange elements in constant time, regardless of the size of the list.

The main advantage of linked lists over other data structures such as arrays is that they can be used to build more complex data structures. For example, linked lists are used to implement stacks, queues, and hash tables.

Linked lists come in different variations, such as singly linked lists, doubly linked lists, and circular linked lists. In a singly linked list, each node has only one pointer to the next node in the list. In a doubly linked list, each node has two pointers, one to the next node and one to the previous node. In a circular linked list, the last node points back to the first node, forming a loop.

Examples: Here is an example schematic of a singly linked list structure:

| 1 | -> | 2 | -> | 3 | -> | 4 | -> NULL

Each node in the linked list has a value and a next pointer that points to the next node in the list. The last node in the list has a next pointer that points to NULL, indicating the end of the list.

Here is an example schematic of a doubly linked list structure:

NULL <--> | 1 | <--> | 2 | <--> | 3 | <--> | 4 | <--> NULL

Each node in the doubly linked list has a value, a prev pointer that points to the previous node in the list, and a next pointer that points to the next node in the list. The first node in the list has a prev pointer that points to NULL, indicating the beginning of the list, and the last node in the list has a next pointer that points to NULL, indicating the end of the list.

We are goining to use this classes to implement a linked list and print_linked_list function to print the linked list.

class Node:
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next = next_node

def print_linked_list(head):
    current = head
    while current is not None:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

1. Insert a value in linked list

Given a sorted linked list and a value to insert, write a function to insert the value in a sorted way.

You are given a sorted linked list of integers and a single integer value. Write a function to insert the value in a sorted way, such that the resulting linked list is also sorted. The function should return a reference to the head of the modified linked list.

Example: Input: linked list: 1 -> 2 -> 4, value to insert: 3 Output: 1 -> 2 -> 3 -> 4

def sorted_insert(head, new_node):

    # Special case for the empty linked list
    if head is None:
        new_node.next = head
        head = new_node

    # Special case for head at end
    elif head.data >= new_node.data:
        new_node.next = head
        head = new_node

    else:
        # Locate the node before the point of insertion
        current = head
        while current.next is not None and current.next.data < new_node.data:
            current = current.next

        new_node.next = current.next
        current.next = new_node

    return head

Explanation:

1. Check if the linked list is empty. If it is, set the head to the new node.
2. If the new node should be inserted at the head of the list, set the new node’s next pointer to the head and update the head to point to the new node.
3. Otherwise, traverse the list starting at the head and find the node whose data value is less than the new node’s data value, but whose next node (if any) has a data value greater than or equal to the new node’s data value.
4. Insert the new node between the found node and its next node (if any). Once the correct position is found, the code updates the links to insert the new node into the linked list. The new_node.next is set to current.next to maintain the remaining linked list after the insertion. Then, current.next is set to new_node to insert the new node between current and current.next.

Space and time complexity:

The time complexity of the sorted_insert function depends on the position where the new node is to be inserted in the sorted linked list. In the best case, when the new node is to be inserted at the beginning of the list, the time complexity is O(1). In the worst case, when the new node is to be inserted at the end of the list or the list is unsorted, the time complexity is O(n), where n is the number of nodes in the linked list.

The space complexity of the sorted_insert function is O(1), since it uses a constant amount of additional space to store the new node and the current node.

Test:

# Test function
def test_sorted_insert():
    # Create linked list: 1 -> 3 -> 4 -> 7
    head = Node(1)
    node1 = Node(3)
    node2 = Node(4)
    node3 = Node(7)
    head.next = node1
    node1.next = node2
    node2.next = node3

    print_linked_list(head)

    # Insert 2: 1 -> 2 -> 3 -> 4 -> 7
    print('insert 2')
    new_node = Node(2)
    head = sorted_insert(head, new_node)
    print_linked_list(head)

    # Insert 0: 0 -> 1 -> 2 -> 3 -> 4 -> 7
    print('insert 0')
    new_node = Node(0)
    head = sorted_insert(head, new_node)
    print_linked_list(head)

    # Insert 8: 0 -> 1 -> 2 -> 3 -> 4 -> 7 -> 8
    print('insert 8')
    new_node = Node(8)
    head = sorted_insert(head, new_node)
    print_linked_list(head)


test_sorted_insert()

1 -> 3 -> 4 -> 7 -> None
insert 2
1 -> 2 -> 3 -> 4 -> 7 -> None
insert 0
0 -> 1 -> 2 -> 3 -> 4 -> 7 -> None
insert 8
0 -> 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> None

2. Delete a given node in Linked List under given constraints

Given a Singly Linked List, write a function to delete a given node. Your function must follow following constraints:

1. It must accept a pointer to the start node as the first parameter and node to be deleted as the second parameter i.e., a pointer to head node is not global.
2. It should not return a pointer to the head node.
3. It should not accept pointer to pointer to the head node. You may assume that the Linked List never becomes empty.

def delete_node(head, data):
    # initialize both temp and prev as head
    temp = head
    prev = head

    # if node to be deleted is head node
    # if it is node just print the fact that head is empty
    # if node is not None we just replace head (temp) with next
    if temp.data == data:
        if temp.next is None:
            # list has only one node and we are removing it
            # so we return None
            return None
        else:
            temp.data = temp.next.data
            temp.next = temp.next.next
            return head

    # move forward prev and temp until:
    # 1. we reach to last node
    # 2. we found match between data
    while temp.next is not None and temp.data != data:
        prev = temp
        temp = temp.next

    # Three main cases:
    # 1. If temp is last value and we don't find match
    if temp.next is None and temp.data != data:
        print("Can't delete the node as it doesn't exist")
        return head
    # 2. If node is last node and we found match
    elif temp.next is None and temp.data == data:
        prev.next = None
        return head
    # 3. Temp is data we want to remove so we pointed prev next to
    # temp next --> removing temp
    else:
        prev.next = temp.next
        return head

Explanation:

The function first initializes two pointers temp and prev to the head of the linked list. It then checks if the node to be deleted is the head node, and if so, it updates the head to the next node. If the node to be deleted is not the head node, it traverses through the linked list until it finds the node with the given data, updating temp and prev pointers as it goes. Once the node is found, the function updates the prev.next pointer to temp.next, effectively removing the node from the linked list.

Space and time complexity:

The time complexity of this function is O(n) where n is the length of the linked list since we may have to traverse through the entire linked list to find the node to be deleted. The space complexity of this function is O(1) since we are only using constant amount of extra space, regardless of the size of the linked list.

Test:

# Test case
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
print_linked_list(head) # 1 2 3 4 5

print('Removing 3')
head = delete_node(head, 3)
print_linked_list(head) # 1 2 4 5

print('Removing 1')
head = delete_node(head, 1)
print_linked_list(head) # 2 4 5

print('Removing 5')
head = delete_node(head, 5)
print_linked_list(head) # 2 4

print('Removing 6')
head = delete_node(head, 6)
print_linked_list(head) # Can't delete the node as it doesn't exist, 2 4

print('Removing 2')
head = delete_node(head, 2)
print_linked_list(head) # Can't delete the node as it doesn't exist, 2 4

print('Removing 4')
head = delete_node(head, 4)
print_linked_list(head) # Can't delete the node as it doesn't exist, 2 4

1 -> 2 -> 3 -> 4 -> 5 -> None
Removing 3
1 -> 2 -> 4 -> 5 -> None
Removing 1
2 -> 4 -> 5 -> None
Removing 5
2 -> 4 -> None
Removing 6
Can't delete the node as it doesn't exist
2 -> 4 -> None
Removing 2
4 -> None
Removing 4
None

3. Compare two strings represented as linked lists

Given two strings, represented as linked lists (every character is a node in a linked list). Write a function compare() that works similar to strcmp(), i.e., it returns 0 if both strings are the same, 1 if the first linked list is lexicographically greater, and -1 if the second string is lexicographically greater.

To compare two strings, you need to compare the characters of the strings in order, from left to right. If the characters at the corresponding positions of both strings are the same, you move on to the next pair of characters. If the characters are different, the string with the lexicographically smaller character is considered to be smaller. If one string ends and the other does not, the shorter string is considered to be smaller. If both strings end at the same position and all characters match, then they are equal.

For example, if the first linked list is “abc” and the second linked list is “abd”, the function should return -1 because “abd” is lexicographically greater than “abc”.

def compare(list1, list2):

    # Traverse both lists. Stop when either end of linked
    # list is reached to end or current characters don't match
    while(list1 and list2 and list1.data == list2.data):
        list1 = list1.next
        list2 = list2.next

    # If both lists are not empty, compare mismatching
    # characters
    if(list1 and list2):
        return 1 if list1.data > list2.data else -1

    # if second string reach end but still string 1 has value
    if (list1 and not list2):
        return 1
    # if first string reach end but still string 2 has value
    if (list2 and not list1):
        return -1
    return 0

Explanation:

The function first initializes two pointers temp and prev to the head of the linked list. It then checks if the node to be deleted is the head node, and if so, it updates the head to the next node. If the node to be deleted is not the head node, it traverses through the linked list until it finds the node with the given data, updating temp and prev pointers as it goes. Once the node is found, the function updates the prev.next pointer to temp.next, effectively removing the node from the linked list.

Space and time complexity:

The time complexity of the code is O(n + m) where n and m are the number of nodes in list1 and list2, respectively. This is because the code traverses both lists once until either the end of a list is reached or characters don’t match.

The space complexity of the code is O(1) since the code only uses a constant amount of memory to store the current nodes being compared.

Test:

# Test case 1: both lists are equal
print("abc vs abc - return 0")
list1 = Node('a')
list1.next = Node('b')
list1.next.next = Node('c')

list2 = Node('a')
list2.next = Node('b')
list2.next.next = Node('c')

if compare(list1, list2) == 0:
    print("test 1 is successfully passed")

# Test case 2: list1 is lexicographically greater
print("abc vs abb - return 1")
list1 = Node('a')
list1.next = Node('b')
list1.next.next = Node('c')

list2 = Node('a')
list2.next = Node('b')
list2.next.next = Node('b')

if compare(list1, list2) == 1:
    print("test 2 is successfully passed")

# Test case 3: list2 is lexicographically greater
print("abb vs abs - return -1")
list1 = Node('a')
list1.next = Node('b')
list1.next.next = Node('b')

list2 = Node('a')
list2.next = Node('b')
list2.next.next = Node('c')

if compare(list1, list2) == -1:
    print("test 3 is successfully passed")

abc vs abc - return 0
test 1 is successfully passed
abc vs abb - return 1
test 2 is successfully passed
abb vs abs - return -1
test 3 is successfully passed

4. Reverse Linked List

Reverse linked list is a process of changing the direction of the linked list, such that the tail node becomes the new head node and every node now points to its previous node. In other words, the “next” pointer of each node now points to its previous node, and the head and tail pointers of the list are swapped.

For example, suppose we have a linked list with nodes containing the values 1, 2, 3, and 4, in that order. The linked list would look like this:

1 -> 2 -> 3 -> 4 -> None

If we reverse this linked list, it would look like this:

4 -> 3 -> 2 -> 1 -> None

Reversing a linked list can be useful in certain situations, such as when we need to iterate over the list in reverse order, or when we need to perform certain operations that are easier to implement in reverse order.

def reverse_linked_list(head):

    prev = None
    current = head

    while current:
        temp = current.next
        current.next = prev
        prev = current
        current = temp

    return prev

Explanation:

The function first initializes two pointers temp and prev to the head of the linked list. It then checks if the node to be deleted is the head node, and if so, it updates the head to the next node. If the node to be deleted is not the head node, it traverses through the linked list until it finds the node with the given data, updating temp and prev pointers as it goes. Once the node is found, the function updates the prev.next pointer to temp.next, effectively removing the node from the linked list.

Space and time complexity:

The time complexity of the code is O(n + m) where n and m are the number of nodes in list1 and list2, respectively. This is because the code traverses both lists once until either the end of a list is reached or characters don’t match.

The space complexity of the code is O(1) since the code only uses a constant amount of memory to store the current nodes being compared.

Test:

def test_reverse_linked_list():
    # Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    head.next.next.next.next = Node(5)

    print(' \n Printing list')
    print_linked_list(head)
    # Reverse the linked list
    reversed_head = reverse_linked_list(head)

    print('\n Printing reversed list')
    # Print the reversed linked list: 5 -> 4 -> 3 -> 2 -> 1
    print_linked_list(reversed_head)

test_reverse_linked_list()

 Printing list
1 -> 2 -> 3 -> 4 -> 5 -> None

 Printing reversed list
5 -> 4 -> 3 -> 2 -> 1 -> None

5. Add two numbers represented by linked lists

• Input:

  • First List: ` 5 -> 6 -> 3`
  • Second List: ` 8 -> 4 -> 2`

• Output

  • Resultant list: ` 1-> 4 -> 0 -> 5`
  • 563 + 842 = 1405

def sum_of_linked_lists(linked_list_one, linked_list_two):
    # reversing lists
    linked_list_one = reverse_linked_list(linked_list_one)
    linked_list_two = reverse_linked_list(linked_list_two)

    new_linked_list = Node(0)
    current_node = new_linked_list
    carry = 0

    node_1 = linked_list_one
    node_2 = linked_list_two

    while node_1 is not None or node_2 is not None or carry != 0:
        value_1 = node_1.data if node_1 is not None else 0
        value_2 = node_2.data if node_2 is not None else 0

        sum_values = value_1 + value_2 + carry

        new_value = sum_values % 10
        new_node = Node(new_value)
        current_node.next = new_node
        current_node = new_node

        carry = sum_values // 10

        node_1 = node_1.next if node_1 is not None else None
        node_2 = node_2.next if node_2 is not None else None

    return reverse_linked_list(new_linked_list.next)

Explanation:

The sum_of_linked_lists function takes two linked lists as input and returns a new linked list that represents the sum of the input linked lists. The input linked lists are first reversed using the reverseList function. Then, a new linked list is created to store the sum, and the nodes of the input linked lists are traversed simultaneously, adding the values of each node and the carry from the previous operation. The result is then stored as a new node in the output linked list. Finally, the output linked list is reversed again to obtain the correct order.

Space and time complexity:

The time complexity of the sum_of_linked_lists function is O(n), where n is the length of the longer input linked list. This is because each node in the longer input linked list is traversed exactly once.

Test:

def test_sum_of_linked_lists():
    # create first linked list: 9 -> 9 -> 9
    linked_list_one = Node(9)
    linked_list_one.next = Node(9)
    linked_list_one.next.next = Node(9)

    # create second linked list: 5 -> 6 -> 3
    linked_list_two = Node(5)
    linked_list_two.next = Node(6)
    linked_list_two.next.next = Node(3)

    # print input linked lists
    print("Input Linked List 1: ", end="")
    print_linked_list(linked_list_one)
    print("Input Linked List 2: ", end="")
    print_linked_list(linked_list_two)

    # get sum of linked lists
    sum_linked_list = sum_of_linked_lists(linked_list_one, linked_list_two)

    # print output linked list
    print("Output Linked List: ", end="")
    print_linked_list(sum_linked_list)


test_sum_of_linked_lists()

Input Linked List 1: 9 -> 9 -> 9 -> None
Input Linked List 2: 5 -> 6 -> 3 -> None
Output Linked List: 1 -> 5 -> 6 -> 2 -> None

6. Reverse a Linked List in groups of given size

This algorithm aims to reverse a singly linked list in groups of a given size k.

For example, if the linked list is 1->2->3->4->5->6->7->8 and the group size is 3, the resulting linked list should be 3->2->1->6->5->4->8->7. If the last group does not have k nodes, leave those nodes as is.

def reverse(head, k):
    if head == None:
        return None
    current_node = head
    next_node = None
    prev_node = None
    count = 0

    while(current_node is not None and count < k):
        next_node = current_node.next
        current_node.next = prev_node
        prev_node = current_node
        current_node = next_node
        count += 1

    if next_node is not None:
        head.next = reverse(next_node, k)

    return prev_node

The reverse function takes two arguments, the head node of a linked list and the size of the groups in which the linked list will be reversed.

• We initialize three variables: current_node which starts at the head node, prev_node which starts as None, and next_node which is initialized as None.
• We also initialize a count variable that will be used to keep track of the number of nodes we’ve reversed.
• We then use a while loop to reverse the linked list in groups of size k. Inside the loop, we first store the next node of the current node in next_node. We then reverse the pointer of the current node to point to the previous node. Finally, we update prev_node to be the current node and move on to the next node.
• If we have reversed k nodes, we have a pointer to the next node in next_node. We then recursively call the reverse function with next_node as the head node to reverse the next group of nodes. We then update the pointer of the current head node to point to the reversed list and return the new head node, which is the last node of the reversed group.
• If there are fewer than k nodes left, we just return the head node as it is.

** Time and Space Complexity:**

The time complexity of this algorithm is O(n), where n is the total number of nodes in the linked list. This is because we traverse each node only once. The space complexity of this algorithm is O(1), since we only use a constant amount of extra space to store the three variables: current_node, prev_node, and next_node.

Test:

# Test case 1
print("\nTest case 1:")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print("Before reverse: ", end="")
print_linked_list(head)
head = reverse(head, 2)
print("After reverse: ", end="")
print_linked_list(head)

# Test case 2
print("\nTest case 2:")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print("Before reverse: ", end="")
print_linked_list(head)
head = reverse(head, 3)
print("After reverse: ", end="")
print_linked_list(head)

# Test case 3
print("\nTest case 3:")
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

print("Before reverse: ", end="")
print_linked_list(head)
head = reverse(head, 1)
print("After reverse: ", end="")
print_linked_list(head)

Test case 1:
Before reverse: 1 -> 2 -> 3 -> 4 -> 5 -> None
After reverse: 2 -> 1 -> 4 -> 3 -> 5 -> None

Test case 2:
Before reverse: 1 -> 2 -> 3 -> 4 -> 5 -> None
After reverse: 3 -> 2 -> 1 -> 5 -> 4 -> None

Test case 3:
Before reverse: 1 -> 2 -> 3 -> 4 -> 5 -> None
After reverse: 1 -> 2 -> 3 -> 4 -> 5 -> None

7. Detect loop in Linked List and return where it begins

Write a function to detect if there is a loop in a given linked list and returns the node where the loop begins if one exists.

A linked list has a loop if any node points to a node that appears earlier in the list, thus forming a cycle.

# etect loop in  Linked List and return where it begins
def detect_cycle(head):
    fast = head
    slow = head
    met_cycle = False

    while fast is not None and fast.next is not None:
        fast = fast.next.next
        slow = slow.next

        if fast == slow:
            met_cycle = True
            break

    if met_cycle == False:
        return None
    else:
        slow = head
        # This time by incrementing on both slow and fast
        # they will meet again in begining of loop
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

Explanation:

The function detect_loop(head) uses the Floyd’s cycle-finding algorithm to detect a loop in the given linked list. It uses two pointers, fast and slow, both initially set to the head of the linked list. fast moves twice as fast as slow by taking two steps at a time while slow moves one step at a time. If there is a loop in the linked list, fast and slow will eventually meet at some point inside the loop.

After detecting the loop, the function resets slow to the head of the linked list and moves both slow and fast one step at a time. When slow and fast meet, the node at which they meet is the start of the loop.

Time and Space Complexity:

The time complexity of this function is O(n) where n is the number of nodes in the linked list. This is because the Floyd’s cycle-finding algorithm takes O(n) time to detect a loop, and the second traversal takes O(n) time as well.

The space complexity is O(1), since the function only uses a constant amount of extra space regardless of the input size.

Test:

# Test case 1
print("\nTest case 1:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
head_node.next.next.next.next.next = head_node.next
node = detect_cycle(head_node)
if node is not None:
    print("Cycle detected at node: " + str(node.data))
else:
    print("No cycle detected")

assert node.data == 2


# Test case 1
print("\nTest case 2:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
head_node.next.next.next.next.next = head_node.next.next
node = detect_cycle(head_node)
if node is not None:
    print("Cycle detected at node: " + str(node.data))
else:
    print("No cycle detected")

assert node.data == 3


# Test case 3
print("\nTest case 3:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
node = detect_cycle(head_node)
if node is not None:
    print("Cycle detected at node: " + str(node.data))
else:
    print("No cycle detected")

assert node is None

Test case 1:
Cycle detected at node: 2

Test case 2:
Cycle detected at node: 3

Test case 3:
No cycle detected

8. Detect and Remove Loop in a Linked List

Write a function to detect if there is a loop in a given linked list and remove it if one exists.

def detect_and_remove_cycle(head):

    fast = head
    slow = head
    met_cycle = False

    while fast is not None and fast.next is not None:
        fast = fast.next.next
        slow = slow.next

        if fast == slow:
            met_cycle = True
            break

    if met_cycle == False:
        return None
    else:
        slow = head
        # This time by incrementing on both slow and fast
        # they will meet again in begining of loop
        while slow != fast:
            slow = slow.next
            fast = fast.next

        print("Cycle detected at node: " + str(slow.data))
        # now both pointer pointed to where cycle started
        # Get pointer to the last node
        while(slow.next != fast):
            slow = slow.next

        # Set the next node of the loop ending node
        # to fix the loop
        slow.next = None

        return slow

Explanation:

The function detect_and_remove_loop(head) uses the Floyd’s cycle-finding algorithm to detect a loop in the given linked list. It uses two pointers, fast and slow, both initially set to the head of the linked list. fast moves twice as fast as slow by taking two steps at a time while slow moves one step at a time. If there is a loop in the linked list, fast and slow will eventually meet at some point inside the loop.

After detecting the loop, the function resets slow to the head of the linked list and moves both slow and fast one step at a time. When slow and fast meet, the node at which they meet is the start of the loop. The function then moves fast one step at a time until it reaches the node before slow. It then sets the next pointer of this node to None, effectively removing the loop.

Time and Space Complexity:

The time complexity of this function is O(n) where n is the number of nodes in the linked list. This is because the Floyd’s cycle-finding algorithm takes O(n) time to detect a loop, and the second traversal takes O(n) time as well.

The space complexity is O(1), since the function only uses a constant amount of extra space regardless of the input size.

Test:

# Test case 1
print("\nTest case 1:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
head_node.next.next.next.next.next = head_node.next
node = detect_and_remove_cycle(head_node)
print("After removing cycle: ", end="")
print_linked_list(head_node)


# Test case 2
print("\nTest case 2:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
head_node.next.next.next.next.next = head_node.next.next
node = detect_and_remove_cycle(head_node)
print("After removing cycle: ", end="")
print_linked_list(head_node)


# Test case 3
print("\nTest case 3:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
node = detect_and_remove_cycle(head_node)
print("After removing cycle: ", end="")
print_linked_list(head_node)

Test case 1:
Cycle detected at node: 2
After removing cycle: 1 -> 2 -> 3 -> 4 -> 5 -> None

Test case 2:
Cycle detected at node: 3
After removing cycle: 1 -> 2 -> 3 -> 4 -> 5 -> None

Test case 3:
After removing cycle: 1 -> 2 -> 3 -> 4 -> 5 -> None

9. Find the middle of a Linked List

Write a function to find the middle node of a singly linked list. If there are two middle nodes, return the second middle node.

# Find the middle node of a linked list
def find_middle_node(head):
    fast = head
    slow = head

    while fast is not None and fast.next is not None:
        fast = fast.next.next
        slow = slow.next

    return slow

Explanation:

The function find_middle(head) uses the Floyd’s cycle-finding algorithm to find the middle node of the given linked list. It uses two pointers, fast and slow, both initially set to the head of the linked list. fast moves twice as fast as slow by taking two steps at a time while slow moves one step at a time. If there is a loop in the linked list, fast and slow will eventually meet at some point inside the loop.

After detecting the loop, the function resets slow to the head of the linked list and moves both slow and fast one step at a time. When slow and fast meet, the node at which they meet is the start of the loop. The function then moves fast one step at a time until it reaches the node before slow. It then sets the next pointer of this node to None, effectively removing the loop.

Time and Space Complexity:

The time complexity of this function is O(n) where n is the number of nodes in the linked list. This is because the Floyd’s cycle-finding algorithm takes O(n) time to detect a loop, and the second traversal takes O(n) time as well.

The space complexity is O(1), since the function only uses a constant amount of extra space regardless of the input size.

Test:

# Test case 1
print("\nTest case 1:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)

middle_node = find_middle_node(head_node)
print("Middle node: " + str(middle_node.data))
assert middle_node.data == 3

# Test case 2
print("\nTest case 2:")
head_node = Node(1)
head_node.next = Node(2)
head_node.next.next = Node(3)
head_node.next.next.next = Node(4)
head_node.next.next.next.next = Node(5)
head_node.next.next.next.next.next = Node(6)
middle_node = find_middle_node(head_node)

print("Middle node: " + str(middle_node.data))
assert middle_node.data == 4

Test case 1:
Middle node: 3

Test case 2:
Middle node: 4

10. Intersection of two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

The problem is to find the intersection point of two linked lists. The input is two singly linked lists represented by their respective heads, headA and headB. If the two lists intersect, then they will have a common node, and the intersection point is defined as the first common node between the two lists. We are supposed to find this common node and return it. If the two lists do not intersect at all, then we need to return null.

Two possible solutions for this problem are presented here. The first implementation has advantages in time complexity, while the second solution has advantages in space complexity.

# O(n + m) time | o(m) space
def get_intersection_node_1(headA, headB):
        if not headA or not headB:
             return None

        # Concatenate A and B
        last = headA
        while last.next:
          last = last.next
        # Atache B to the last.next
        last.next = headB

        # Find the start of the loop
        fast = slow = headA
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                fast = headA
                while fast != slow:
                    slow, fast = slow.next, fast.next
                last.next = None
                return slow

        # No loop found
        last.next = None
        return None

# O(nm) time | o(1) space
def get_intersection_node_2(headA, headB):
        nodes_in_B = set()

        while headB is not None:
            nodes_in_B.add(headB)
            headB = headB.next

        while headA is not None:
            # if we find the node pointed to by headA,
            # in our set containing nodes of B, then return the node
            if headA in nodes_in_B:
                return headA
            headA = headA.next

        return None

Explanation:

The first implementation has O(n+m) time complexity and O(m) space complexity. In this implementation, we concatenate list A and list B, which makes the new list have a loop at the point where list B connects with list A. Then we use Floyd’s cycle detection algorithm to detect the loop and find the start of the loop. The start of the loop is the intersection point of list A and list B. Finally, we break the loop by setting the next node of the last node to None.

The second implementation has O(nm) time complexity and O(1) space complexity. In this implementation, we use two nested loops to iterate over each node in list A and list B. For each node in list A, we check if it is present in the set of nodes in list B. If we find a node that is present in both lists, we return that node as the intersection point. If we have iterated over all nodes and haven’t found any common node, we return null.

test:

# test case 1
print("\nTest case 1:")
head_node_1 = Node(1)
head_node_1.next = Node(2)
head_node_1.next.next = Node(3)
head_node_1.next.next.next = Node(4)
head_node_1.next.next.next.next = Node(5)

head_node_2 = Node(6)
head_node_2.next = Node(7)
head_node_2.next.next = head_node_1.next.next

intersection_node_1 = get_intersection_node_1(head_node_1, head_node_2)
intersection_node_2 = get_intersection_node_2(head_node_1, head_node_2)

print("Intersection node (function 1): " + str(intersection_node_1.data))
print("Intersection node (function 2): " + str(intersection_node_2.data))

assert intersection_node_1.data == 3
assert intersection_node_2.data == 3

# test case 2
print("\nTest case 2:")
head_node_1 = Node(1)
head_node_1.next = Node(2)
head_node_1.next.next = Node(3)
head_node_1.next.next.next = Node(4)
head_node_1.next.next.next.next = Node(5)

head_node_2 = Node(6)
head_node_2.next = Node(7)
head_node_2.next.next = Node(8)
head_node_2.next.next.next = Node(9)
head_node_2.next.next.next.next = Node(10)
head_node_2.next.next.next.next.next = Node(11)
head_node_2.next.next.next.next.next.next = head_node_1.next.next.next.next

intersection_node_1 = get_intersection_node_1(head_node_1, head_node_2)
intersection_node_2 = get_intersection_node_2(head_node_1, head_node_2)

print("Intersection node (function 1): " + str(intersection_node_1.data))
print("Intersection node (function 2): " + str(intersection_node_2.data))

assert intersection_node_1.data == 5
assert intersection_node_2.data == 5

Test case 1:
Intersection node (function 1): 3
Intersection node (function 2): 3

Test case 2:
Intersection node (function 1): 5
Intersection node (function 2): 5

now we found intersect, let’s see how to find union of two linked list:

# getUnionNode
def get_union_node(headA, headB):
    nodes_set = set()
    current = headA
    while current:
        nodes_set.add(current.data)
        current = current.next

    current = headB
    while current:
        nodes_set.add(current.data)
        current = current.next

    # Create the new linked list from the set of unique nodes
    new_head = Node(None)
    current = new_head
    for val in nodes_set:
        current.next = Node(val)
        current = current.next

    return new_head.next

Explanation:

The function union(headA, headB) returns the union of two linked lists. It uses a set to store the nodes of the first linked list. Then it iterates over the second linked list and adds the nodes that are not already present in the set to the union list. Finally, it returns the union list.

Time and Space Complexity:

The time complexity of this function is O(n+m) where n and m are the number of nodes in the two linked lists. This is because the function iterates over both lists once, and the time complexity of adding a node to a set is O(1).

The space complexity is O(n+m), since the function uses a set to store the nodes of the first linked list, and the union list can have at most n+m nodes.

Test:

# Test Case 1
print("\nTest case 1:")
# List A: 1 -> 2 -> 3 -> 4 -> 5 -> 6
# List B: 2 -> 3 -> 4 -> 5 -> 6
# Intersection Point: 2

a = Node(1)
a.next = Node(2)
a.next.next = Node(3)
a.next.next.next = Node(4)
a.next.next.next.next = Node(5)
a.next.next.next.next.next = Node(6)

b = Node(2)
b.next = Node(3)
b.next.next = Node(4)
b.next.next.next = Node(5)
b.next.next.next.next = Node(6)

print('List A:')
print_linked_list(a)
print('List B:')
print_linked_list(b)
print('Union Node:')
print_linked_list(get_union_node(a, b))


# Test Case 2
print("\nTest case 2:")
# List A: 1 -> 2 -> 3 -> 4 -> 5 -> 6
# List B: 7 -> 8 -> 9
# Intersection Point: None

a = Node(1)
a.next = Node(2)
a.next.next = Node(3)
a.next.next.next = Node(4)
a.next.next.next.next = Node(5)
a.next.next.next.next.next = Node(6)

b = Node(7)
b.next = Node(8)
b.next.next = Node(9)

print('List A:')
print_linked_list(a)
print('List B:')
print_linked_list(b)
print('Union Node:')
print_linked_list(get_union_node(a, b))


# Test Case 3
print("\nTest case 3:")
# List A: 11 -> 1 -> 9 -> 5 -> 5 -> 9 -> 1 -> 4
# List B: 7 -> 8 -> 9
# Intersection Point: None


a = Node(11)
a.next = Node(1)
a.next.next = Node(9)
a.next.next.next = Node(5)
a.next.next.next.next = Node(5)
a.next.next.next.next.next = Node(9)
a.next.next.next.next.next.next = Node(1)
a.next.next.next.next.next.next.next = Node(4)

b = Node(7)
b.next = Node(8)
b.next.next = Node(9)

print('List A:')
print_linked_list(a)
print('List B:')
print_linked_list(b)
print('Union Node:')
print_linked_list(get_union_node(a, b))

Test case 1:
List A:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
List B:
2 -> 3 -> 4 -> 5 -> 6 -> None
Union Node:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

Test case 2:
List A:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
List B:
7 -> 8 -> 9 -> None
Union Node:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> None

Test case 3:
List A:
11 -> 1 -> 9 -> 5 -> 5 -> 9 -> 1 -> 4 -> None
List B:
7 -> 8 -> 9 -> None
Union Node:
1 -> 4 -> 5 -> 7 -> 8 -> 9 -> 11 -> None

11. Merge two sorted Linked Lists

Given the heads of two sorted linked lists headA and headB, return the sorted linked list formed by merging both lists in ascending order.

The problem is to merge two sorted linked lists into a single sorted linked list. The input is two singly linked lists represented by their respective heads, headA and headB. We are supposed to merge these two lists into a single sorted linked list and return the head of the merged list.

Let’s write both recursive and iterative solutions for this problem.

#  Iterative
# O(n + m) time | O(1) space
def merge_sorted_linked_lists_iterative(head1, head2):
    prev_node = None
    curr1 = head1
    curr2 = head2
    while curr1 is not None and curr2 is not None:
        # if curr1 is less than curr2 we just move forward in
        # curr2 and don't need to switch curr2 with curr1
        if curr1.data < curr2.data:
            prev_node = curr1
            curr1 = curr1.next
        else:
            # because we started prev_node from None
            if prev_node is not None:
                prev_node.next = curr2
            # now we switch prev_node with curr2
            prev_node = curr2
            curr2 = curr2.next
            prev_node.next = curr1
    # when we ran out of value in first linked list
    # we just append whole curr2 to curr1
    if curr1 is None:
        prev_node.next = curr2

    return head1 if head1.data < head2.data else head2


# Recursive
# O(n + m) time | O(n + m) space - where n is the number of nodes in the first
# Linked List and m is the number of nodes in the second Linked List
def merge_sorted_linked_list_recursive(head_one, head_two):
    recursive_merge(head_one, head_two, None)
    return head_one if head_one.data < head_two.data else head_two


def recursive_merge(curr1, curr2, prev_node):
    if curr1 is None:
        prev_node.next = curr2
        return
    if curr2 is None:
        return

    if curr1.data < curr2.data:
        recursive_merge(curr1.next, curr2, curr1)
    else:
        if prev_node is not None:
            prev_node.next = curr2
        new_curr2 = curr2.next
        curr2.next = curr1
        recursive_merge(curr1, new_curr2, curr2)

Explanation:

For the iterative implementation, we initialize prev_node to None, and pointers curr1 and curr2 to the heads of the two linked lists. We then loop through the lists as long as curr1 and curr2 are not None. Inside the loop, we check if the value at curr1 is less than the value at curr2. If it is, we just move forward with curr1. If not, we link prev_node to curr2, update prev_node to curr2, move forward with curr2, and link prev_node to curr1. Once we’ve reached the end of the first linked list, we append the remaining nodes of the second linked list to the end of the first linked list. Finally, we return the head of the merged linked list.

For the recursive implementation, we initialize pointers curr1 and curr2 to the heads of the two linked lists and prev_node to None. We then define a recursive helper function recursive_merge that takes three arguments: the current node of the first linked list (curr1), the current node of the second linked list (curr2), and the previous node of the first linked list (prev_node). We check if either curr1 or curr2 is None. If either one is, we just return. Otherwise, we check if the value at curr1 is less than the value at curr2. If it is, we call recursive_merge withcurr1.next, curr2, and curr1 as arguments. If not, we link prev_node to curr2, update prev_node to curr2, and then call recursive_merge with curr1, curr2.next, and curr2 as arguments. Finally, we return the head of the merged linked list.

Time and Space Complexity:

The time complexity for both implementations is O(n + m), where n is the number of nodes in the first linked list and m is the number of nodes in the second linked list. The space complexity for the iterative implementation is O(1) because we’re only using a few constant variables. The space complexity for the recursive implementation is O(n + m) because of the recursive calls.

Test:

# Test 1
n1 = Node(1)
n2 = Node(2)
n3 = Node(4)
n4 = Node(1)
n5 = Node(3)
n6 = Node(4)

n1.next = n2
n2.next = n3
n4.next = n5
n5.next = n6

print_linked_list(merge_sorted_linked_lists_iterative(n1, n4))  # Output: 1 1 2 3 4 4

# Test 2
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)

n1.next = n2
n2.next = n3
n4.next = n5

print_linked_list(merge_sorted_linked_list_recursive(n1, n4))  # Output: 1 2 3 4 5

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None
1 -> 2 -> 3 -> 4 -> 5 -> None