Sort List - Java Solution

1. Introduction

This post explores the "Sort List" problem, a classic challenge in linked list manipulation. The objective is to sort a given linked list in ascending order. This problem tests one's understanding of linked list operations as well as sorting algorithms, particularly in a linked list context.

Problem

Given the head of a linked list, the task is to return the list after sorting it in ascending order. The challenge is to perform the sorting efficiently while working within the constraints of the linked list data structure.

2. Solution Steps

1. Implement a merge sort algorithm on the linked list, as it provides O(n log n) complexity, ideal for sorting linked lists.

2. The process involves splitting the list into two halves, sorting each half, and then merging the sorted halves.

3. Use a fast and slow pointer approach to find the middle of the list for splitting.

4. Recursively split the list until individual nodes are obtained.

5. Merge the sorted halves by comparing nodes and rearranging the pointers.

6. Continue merging until the entire list is sorted and combined.

3. Code Program

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class SortList {
    public static void main(String[] args) {
        // Example use case
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode sorted = sortList(head);
        while (sorted != null) {
            System.out.print(sorted.val + " ");
            sorted = sorted.next;
        }
    }

    // Function to sort the linked list using merge sort
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // Step 1: Split the list into halves
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;

        // Step 2: Sort each half
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        // Step 3: Merge the sorted halves
        return merge(l1, l2);
    }

    // Function to merge two sorted linked lists
    private static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        return dummy.next;
    }
}

Output:

1 2 3 4

Explanation:

1. sortList: This function sorts a linked list using the merge sort algorithm. It first finds the middle of the list, then recursively sorts the two halves, and finally merges them back together.

2. The list is split into two halves using a slow and fast pointer approach. The slow pointer moves one step at a time, while the fast pointer moves two steps, finding the middle when the fast pointer reaches the end.

3. The merge function takes two sorted lists and merges them into a single sorted list. It iteratively compares the nodes of the two lists, appending the smaller node to the merged list.

4. The process of splitting, sorting, and merging is repeated recursively until the entire list is sorted.

5. This approach is efficient for linked lists, as merge sort has O(n log n) complexity and does not require additional space for array indices.