# Mastering Linked Lists: 11 Algorithms for Efficient Data Manipulation

** Published:**

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:**

- Check if the linked list is empty. If it is, set the head to the new node.
- 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.
- 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.
- 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:

- 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.
- It should not return a pointer to the head node.
- 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 with`curr1.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
```