Day 10

Day 10: Advanced Linked List Operations and Problems

Intermediate 12 min

10/60 Days

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 …

Advanced Linked List Operations and Problems#

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!

Solution#

The worked solution is a lifetime-access perk. Unlock all 60 solutions. Already purchased? Log in to view it.

Show the solution

 1class Node:
 2    def __init__(self, data):
 3        self.data = data
 4        self.next = None
 5
 6
 7def detect_and_remove_loop(head):
 8    slow = fast = head
 9    while fast and fast.next:
10        slow = slow.next
11        fast = fast.next.next
12        if slow is fast:  # loop found
13            break
14    else:
15        return head  # no loop
16
17    # Move one pointer to head, advance both until they meet at loop start
18    slow = head
19    if slow is fast:  # loop starts at head
20        while fast.next is not slow:
21            fast = fast.next
22    else:
23        while slow.next is not fast.next:
24            slow = slow.next
25            fast = fast.next
26    fast.next = None  # break the loop
27    return head
28
29
30def add_two_numbers(l1, l2):
31    dummy = Node(0)
32    current = dummy
33    carry = 0
34    while l1 or l2 or carry:
35        total = carry
36        if l1:
37            total += l1.data
38            l1 = l1.next
39        if l2:
40            total += l2.data
41            l2 = l2.next
42        carry, digit = divmod(total, 10)
43        current.next = Node(digit)
44        current = current.next
45    return dummy.next
46
47
48def is_palindrome(head):
49    values = []
50    while head:
51        values.append(head.data)
52        head = head.next
53    return values == values[::-1]

detect_and_remove_loop uses Floyd’s cycle detection to find the meeting point, then locates the loop start and severs it: O(n) time and O(1) space. add_two_numbers walks both lists once while tracking a carry, since the digits are stored least significant first, giving O(max(n, m)) time. is_palindrome here copies values into a list and compares against its reverse for O(n) time and O(n) space.

Keep your momentum going

Create a free account to unlock the full lesson, all 60 days, and track your progress as you go.