1. Introduction

Linked lists are a common data structure that can be used to store a collection of items. There are times when we need to rearrange a linked list in increasing order, such as for sorting purposes. In this blog post, we will explore a solution to rearrange a linked list in increasing order using Java.

2. Program Steps

1. Define a Node class to represent each element in the linked list.

2. Create helper functions: insert (to insert nodes) and printList (to print the linked list).

3. Use the merge sort algorithm to sort the linked list in increasing order.

4. The merge sort algorithm will involve breaking the list into two halves, recursively sorting each half, and then merging the two sorted halves together.

3. Code Program

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListSort {

    Node head;

    // Inserts a new Node at the end of the list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    // Merges two sorted lists
    public Node merge(Node a, Node b) {
        if (a == null) return b;
        if (b == null) return a;

        Node result;
        if (a.data <= b.data) {
            result = a;
            result.next = merge(a.next, b);
        } else {
            result = b;
            result.next = merge(a, b.next);
        }
        return result;
    }

    // Main function for sorting the linked list
    public Node mergeSort(Node node) {
        if (node == null || node.next == null) return node;

        Node middle = getMiddle(node);
        Node nextOfMiddle = middle.next;
        middle.next = null;

        Node left = mergeSort(node);
        Node right = mergeSort(nextOfMiddle);

        Node sortedList = merge(left, right);
        return sortedList;
    }

    // Get middle of the linked list
    public Node getMiddle(Node node) {
        if (node == null) return node;

        Node slow = node, fast = node;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Print the linked list
    public void printList(Node node) {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        LinkedListSort list = new LinkedListSort();
        list.insert(4);
        list.insert(2);
        list.insert(7);
        list.insert(1);
        list.insert(5);

        System.out.println("Linked List before sorting:");
        list.printList(list.head);

        list.head = list.mergeSort(list.head);

        System.out.println("\nLinked List after sorting:");
        list.printList(list.head);
    }
}

Output:

Linked List before sorting:
4 2 7 1 5
Linked List after sorting:
1 2 4 5 7

4. Step By Step Explanation

1. We start by defining a Node class which has two properties: data and next.

2. In the LinkedListSort class, we maintain a head pointer to the beginning of the list.

3. The insert method allows us to insert elements into the list.

4. The mergeSort function is the main function that implements the merge sort algorithm. It recursively divides the list into two halves until each sublist contains a single element.

5. The merge function is responsible for merging two sorted linked lists.

6. The getMiddle function finds the middle of the linked list using the fast and slow pointer technique.

7. In the main method, we create a linked list, print it, sort it, and then print the sorted linked list.