Advanced Linked List Operations and Problems
Welcome to Day 10 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore advanced operations and tackle common problems related to linked lists. These topics are frequently encountered in coding interviews and real-world applications.
1. Reversing a Linked List
Reversing a linked list is a fundamental operation that’s often asked in interviews. Here’s an implementation for a singly linked list:
1def reverse_linked_list(self):
2 prev = None
3 current = self.head
4 while current:
5 next_node = current.next
6 current.next = prev
7 prev = current
8 current = next_node
9 self.head = prev
Time Complexity: O(n), where n is the number of nodes in the list.
2. Detecting a Cycle in a Linked List
The Floyd’s Cycle-Finding Algorithm, also known as the “tortoise and hare” algorithm, is an efficient method to detect cycles:
1def has_cycle(self):
2 if not self.head:
3 return False
4
5 slow = self.head
6 fast = self.head.next
7
8 while slow != fast:
9 if not fast or not fast.next:
10 …
Advanced Linked List Operations and Problems
Welcome to Day 10 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore advanced operations and tackle common problems related to linked lists. These topics are frequently encountered in coding interviews and real-world applications.
1. Reversing a Linked List
Reversing a linked list is a fundamental operation that’s often asked in interviews. Here’s an implementation for a singly linked list:
1def reverse_linked_list(self):
2 prev = None
3 current = self.head
4 while current:
5 next_node = current.next
6 current.next = prev
7 prev = current
8 current = next_node
9 self.head = prev
Time Complexity: O(n), where n is the number of nodes in the list.
2. Detecting a Cycle in a Linked List
The Floyd’s Cycle-Finding Algorithm, also known as the “tortoise and hare” algorithm, is an efficient method to detect cycles:
1def has_cycle(self):
2 if not self.head:
3 return False
4
5 slow = self.head
6 fast = self.head.next
7
8 while slow != fast:
9 if not fast or not fast.next:
10 return False
11 slow = slow.next
12 fast = fast.next.next
13
14 return True
Time Complexity: O(n), Space Complexity: O(1)
3. Finding the Middle Node
Finding the middle node is another common problem. We can solve it efficiently using two pointers:
1def find_middle(self):
2 if not self.head:
3 return None
4
5 slow = fast = self.head
6 while fast.next and fast.next.next:
7 slow = slow.next
8 fast = fast.next.next
9
10 return slow
Time Complexity: O(n), Space Complexity: O(1)
4. Merging Two Sorted Linked Lists
This operation is useful in many algorithms, including merge sort for linked lists:
1def merge_sorted_lists(list1, list2):
2 dummy = Node(0)
3 current = dummy
4
5 while list1 and list2:
6 if list1.data <= list2.data:
7 current.next = list1
8 list1 = list1.next
9 else:
10 current.next = list2
11 list2 = list2.next
12 current = current.next
13
14 if list1:
15 current.next = list1
16 if list2:
17 current.next = list2
18
19 return dummy.next
Time Complexity: O(n + m), where n and m are the lengths of the two lists.
5. Removing Nth Node from End
This problem demonstrates the use of two pointers with a specific gap:
1def remove_nth_from_end(self, n):
2 dummy = Node(0)
3 dummy.next = self.head
4 first = second = dummy
5
6 # Advance first pointer by n+1 steps
7 for i in range(n + 1):
8 if not first:
9 return self.head
10 first = first.next
11
12 # Move both pointers until first reaches the end
13 while first:
14 first = first.next
15 second = second.next
16
17 # Remove the target node
18 second.next = second.next.next
19
20 return dummy.next
Time Complexity: O(L), where L is the length of the list.
6. Flattening a Multilevel Doubly Linked List
This problem involves working with a more complex linked list structure:
1class Node:
2 def __init__(self, val, prev=None, next=None, child=None):
3 self.val = val
4 self.prev = prev
5 self.next = next
6 self.child = child
7
8def flatten(head):
9 if not head:
10 return head
11
12 current = head
13 while current:
14 if current.child:
15 next_node = current.next
16 child = flatten(current.child)
17 current.next = child
18 child.prev = current
19 current.child = None
20
21 while current.next:
22 current = current.next
23
24 current.next = next_node
25 if next_node:
26 next_node.prev = current
27
28 current = current.next
29
30 return head
Time Complexity: O(N), where N is the total number of nodes in the multilevel structure.
Exercise
- Implement a function to detect and remove a loop in a linked list.
- Write a method to add two numbers represented by linked lists. The digits are stored in reverse order, and each node contains a single digit.
- Implement a function to determine if a linked list is a palindrome.
Summary
Today, we explored advanced linked list operations and problems that are commonly encountered in coding interviews and real-world scenarios. These problems demonstrate various techniques, including two-pointer approaches, dummy nodes, and recursive solutions. Understanding these concepts will significantly improve your problem-solving skills with linked lists.
Tomorrow, we’ll shift our focus to a new data structure: stacks. We’ll explore their implementation and applications in solving various problems. Stay tuned!