Detailed explanation of the implementation of linked list inversion and merge operations in Python

Preface

Using Python to implement reverse linked lists and merge linked lists is common in development. Let’s first look at their respective application scenarios.

1. Reverse the link list

For example, when processing time series data, sometimes it is necessary to display historical data in order from near to far. If the data is stored in the form of a linked list, this requirement can be efficiently achieved by inverting the linked list. For example, when determining whether a linked list is a palindromic list (that is, the values of the positive and reverse order traversal of the linked list are the same), you can first reverse the second half of the linked list and then compare it with the first half. For example, in image processing, it is sometimes necessary to flip the image horizontally or vertically. If the image data is stored in a linked list (for example, each node in the linked list represents one pixel of the image), inverting the linked list can achieve horizontal flipping of the image.

2. Merge the linked list

For example, in large-scale data sorting, when the amount of data is too large to be loaded into memory at one time, a multi-channel merge sorting algorithm can be used. The algorithm divides the data into multiple small pieces, sorts them separately to obtain multiple ordered linked lists, and then obtains the final ordered results by merging these ordered linked lists. Merging linked lists is one of the core operations of multiple merge sorting. In a database, when multiple query operations are performed and multiple ordered result sets are obtained, these result sets need to be merged into an ordered result set. If these result sets are stored in linked lists, merging linked lists can effectively accomplish this task. In multimedia processing, it is sometimes necessary to combine multiple audio and video streams into one stream. If the data of each audio and video stream is stored in a linked list, the merged linked list can realize the merge of audio and video streams.

After understanding the application scenarios of reverse link lists and merged link lists, is it the same as Brother V? This thing is really useful. Next, Brother V will introduce a reverse link list and merged link list in detail.

Reverse link list

Let’s first look at implementing inverted linked lists in Python. We can use iterative and recursive methods. The detailed implementation of these two methods is given below.

Iteration method

The core idea of the iterative method is to traverse the linked list, and during the traversal process, change the pointer direction of each node so that it points to the previous node.

# Define the linked list node classclass ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def reverseList(head):
    # Initialize the previous node to None    prev = None
    # The current node points to the header node    curr = head
    while curr:
        # Save the next node of the current node        next_node = 
        # Point the pointer of the current node to the previous node         = prev
        # The previous node moves to the current node        prev = curr
        # The current node moves to the next node        curr = next_node
    # Finally prev points to the inverted header node    return prev

# Helper function: Convert list to linked tabledef list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
         = ListNode(val)
        current = 
    return 

# Helper function: Convert linked list to listdef linked_list_to_list(head):
    result = []
    current = head
    while current:
        ()
        current = 
    return result

# Test codeinput_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # Output: [5, 4, 3, 2, 1]

Recursive method

The core idea of the recursive method is to recursively reverse the linked list after the current node, and then point the pointer of the current node to the previous node.

# Define the linked list node classclass ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def reverseList(head):
    # If the linked list is empty or there is only one node, return directly to the header node    if not head or not :
        return head
    # Recursively reverse the linked list after the current node    new_head = reverseList()
    # Point the pointer of the next node of the current node to the current node     = head
    # Set the pointer of the current node to None     = None
    return new_head

# Helper function: Convert list to linked tabledef list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
         = ListNode(val)
        current = 
    return 

# Helper function: Convert linked list to listdef linked_list_to_list(head):
    result = []
    current = head
    while current:
        ()
        current = 
    return result

# Test codeinput_list = [1, 2, 3, 4, 5]
head = list_to_linked_list(input_list)
reversed_head = reverseList(head)
output_list = linked_list_to_list(reversed_head)
print(output_list)  # Output: [5, 4, 3, 2, 1]

Both of the above methods can realize the inversion of the linked list. The time complexity of the iteration method is O(n) and the space complexity is O(1); the time complexity of the recursive method is also O(n), but the space complexity is O(n), which is mainly the overhead of the recursive call stack.

Use Python to implement the merge of linked lists

In Python, the common situations are to merge two ordered linked lists and merge multiple ordered linked lists. The following are the implementation methods of these two situations.

Merge two ordered link lists

The idea of merging two ordered linked lists is to compare the values of the current nodes of the two linked lists, add the smaller nodes to the result linked list, and then move the pointer of the corresponding linked list until one of the linked lists is traversed, and finally connect the remaining part of the other linked list directly to the end of the result linked list.

# Define the linked list node classclass ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def mergeTwoLists(l1, l2):
    # Create a virtual header node    dummy = ListNode(0)
    # The current node pointer, initially pointing to the virtual header node    current = dummy
    while l1 and l2:
        if  &lt;= :
            # If the value of l1 is small, add the l1 node to the result link table             = l1
            l1 = 
        else:
            # If the value of l2 is small, add the l2 node to the result link table             = l2
            l2 = 
        # Move the current node pointer        current = 
    # Connect the remaining linked list to the end of the result linked list    if l1:
         = l1
    if l2:
         = l2
    # Return to the head node of the merged linked list (the next node of the virtual head node)    return 

# Helper function: Convert list to linked tabledef list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
         = ListNode(val)
        current = 
    return 

# Helper function: Convert linked list to listdef linked_list_to_list(head):
    result = []
    current = head
    while current:
        ()
        current = 
    return result

# Test codelist1 = [1, 2, 4]
list2 = [1, 3, 4]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 1, 2, 3, 4, 4]

Merge multiple ordered link lists

To merge multiple ordered linked lists, you can use the method of dividing and consolidation to continuously merge the linked lists in pairs until they are finally merged into one linked list.

# Define the linked list node classclass ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if  &lt;= :
             = l1
            l1 = 
        else:
             = l2
            l2 = 
        current = 
    if l1:
         = l1
    if l2:
         = l2
    return 

def mergeKLists(lists):
    if not lists:
        return None
    while len(lists) &gt; 1:
        merged_lists = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 &lt; len(lists) else None
            merged = mergeTwoLists(l1, l2)
            merged_lists.append(merged)
        lists = merged_lists
    return lists[0]

# Helper function: Convert list to linked tabledef list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
         = ListNode(val)
        current = 
    return 

# Helper function: Convert linked list to listdef linked_list_to_list(head):
    result = []
    current = head
    while current:
        ()
        current = 
    return result

# Test codelists = [[1, 4, 5], [1, 3, 4], [2, 6]]
linked_lists = [list_to_linked_list(lst) for lst in lists]
merged_head = mergeKLists(linked_lists)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 1, 2, 3, 4, 4, 5, 6]

The above code implements the functions of merging two ordered linked lists and merging multiple ordered linked lists respectively. Through auxiliary functions, the conversion between linked lists and lists can be easily performed, which is convenient for testing.

In the process of merging two linked lists, do you need to consider the case that the linked list is empty?

In the process of merging two linked lists, it is necessary to consider the case that the linked list is empty. The following is a detailed analysis from the necessity and different implementation situations:

necessity

It is very necessary to consider the case where the linked list is empty, for the following reasons:

Avoid program errors: If the linked list is not processed, directly access the node properties of the empty linked list in the code (such asvalornext) will triggerAttributeErrorException, causing the program to crash.
Ensure logical integrity: In practical applications, the empty linked list is a reasonable input situation. Handling this boundary situation can make the code more robust and adapt to various input scenarios.

Handling of different implementation situations

Merge two ordered link lists

The following is the code for merging two ordered linked lists considering the case of null links:

class ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def mergeTwoLists(l1, l2):
    # Create a virtual header node    dummy = ListNode(0)
    current = dummy
    # Handle the situation where the linked list is empty    if not l1:
        return l2
    if not l2:
        return l1
    while l1 and l2:
        if  &lt;= :
             = l1
            l1 = 
        else:
             = l2
            l2 = 
        current = 
    if l1:
         = l1
    if l2:
         = l2
    return 

# Helper function: Convert list to linked tabledef list_to_linked_list(lst):
    dummy = ListNode(0)
    current = dummy
    for val in lst:
         = ListNode(val)
        current = 
    return 

# Helper function: Convert linked list to listdef linked_list_to_list(head):
    result = []
    current = head
    while current:
        ()
        current = 
    return result

# Test the case where the linked list is emptylist1 = []
list2 = [1, 2, 3]
l1 = list_to_linked_list(list1)
l2 = list_to_linked_list(list2)
merged_head = mergeTwoLists(l1, l2)
merged_list = linked_list_to_list(merged_head)
print(merged_list)  # Output: [1, 2, 3]

In the above code, the link list is judged at the beginning of the function. If one of the linked lists is empty, it will directly return to the other link list. This can avoid errors in subsequent codes when accessing empty linked list nodes.

Recursively implementing merge two ordered linked lists

class ListNode:
    def __init__(self, val=0, next=None):
         = val
         = next

def mergeTwoLists(l1, l2):
    # Handle the situation where the linked list is empty    if not l1:
        return l2
    if not l2:
        return l1
    if  &lt;= :
         = mergeTwoLists(, l2)
        return l1
    else:
         = mergeTwoLists(l1, )
        return l2

# Helper function omitted, same as above code

In recursive implementation, the case where the linked list is empty is also processed at the beginning of the function to ensure that there will be no errors in accessing the empty node attributes when calling recursively.

Therefore, when merging two linked lists, it is essential to consider the case where the linked list is empty, which can enhance the robustness and reliability of the code.

at last

Reversing linked lists and merging linked lists are the basic and important algorithms in linked list operations. They have wide uses in many practical application scenarios, such as the application scenarios introduced at the beginning of Brother V's article. If you don't understand the application scenarios to learn linked list reversing and merging, even if you master the implementation principles, you only learn the moves, but don't understand why.

The above is the detailed explanation of Python's implementation of linked list inversion and merge operations. For more information about Python linked lists, please pay attention to my other related articles!