sort a linked list in python

To sort a linked list in Python, we can use any of the standard sorting algorithms like merge sort, quick sort, or insertion sort. Here, we will provide an implementation for merge sort.

First, we define a ListNode class to represent each node in the linked list.


main.py
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
106 chars
5 lines

Next, we define a merge_sort function that takes a linked list and returns a sorted linked list. The function implements merge sort using recursion.


main.py
def merge_sort(head):
    if head is None or head.next is None:
        return head
    
    # divide the linked list into two halves
    mid = get_middle(head)
    left = head
    right = mid.next
    mid.next = None
    
    # recursively sort the two halves
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # merge the sorted halves
    return merge(left_sorted, right_sorted)
412 chars
17 lines

The get_middle function calculates the middle node of the linked list, which is then used to divide the list into two halves.


main.py
def get_middle(head):
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow
156 chars
7 lines

The merge function merges two sorted linked lists into a single sorted linked list.


main.py
def merge(left, right):
    dummy = ListNode()
    curr = dummy
    
    while left and right:
        if left.val < right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next
        curr = curr.next
    
    if left:
        curr.next = left
    else:
        curr.next = right
    
    return dummy.next
392 chars
20 lines

Finally, we can test the merge_sort function by creating a linked list and calling the function.


main.py
head = ListNode(3)
head.next = ListNode(1)
head.next.next = ListNode(4)
head.next.next.next = ListNode(2)

sorted_list = merge_sort(head)

while sorted_list:
    print(sorted_list.val)
    sorted_list = sorted_list.next
220 chars
11 lines