QuickSortLinkedList.java

/* File:    SortLinkedList.java
 * Created: 8/21/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart Inc.
 */

//=======================================================================================

/**
 * @author  Sabbir Manandhar
 *          manandharsabbir@gmail.com
 * @version 1.0
 */
public class QuickSortLinkedList {

  /**
   * main method
   * @param args
   */
  public static void main(String[] args) {
    ListNode head = new ListNode(6);
    ListNode newNode = new ListNode(7);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(1);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(3);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(2);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(9);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(23);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(5);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(5);
    newNode.next = head;
    head = newNode;

    newNode = new ListNode(15);
    newNode.next = head;
    head = newNode;

    System.out.println(sort(head));
  } // main

  //-------------------------------------------------------------------------------------

  /**
   * Method to sort
   * @param head head of the list to sort
   * @return head of sorted list
   */
  public static ListNode sort(ListNode head) {
    return sortHelper(head)[0];
  } // sort

  //-------------------------------------------------------------------------------------

  /**
   * Recursive helper method to sort the list. Recursively sorts the partitioned lists
   * and finally return the merged list which is sorted.
   * Average Case Time Complexity is O(nLogn) and Space Complexity is O(1)
   * @param head
   * @return
   */
  public static ListNode[] sortHelper(ListNode head) {
    if (head == null || head.next == null) return new ListNode[]{head, head};

    ListNode[] partitions = partition(head);
    ListNode[] firstHeadTail = sortHelper(partitions[0]);
    ListNode[] secondHeadTail = sortHelper(partitions[2]);
    return merge(firstHeadTail, partitions[1], secondHeadTail);
  } // sortHelper

  //-------------------------------------------------------------------------------------

  /**
   * Merges Two sorted lists and a pivot in between them. First list contains elements smaller than
   * or equal to pivot and Seconds list contains elements greater than pivot
   * Takes O(1) time and O(1) space
   *
   * @param firstHeadTail Array of Head and Tail Nodes of first sorted list
   * @param pivot Pivot node
   * @param secondHeadTail Array of Head and Tail Nodes of seconds sorted list
   * @return
   */
  public static ListNode[] merge(ListNode[] firstHeadTail, ListNode pivot, ListNode[] secondHeadTail) {
    if (firstHeadTail[1] != null && secondHeadTail[1] != null) {
      firstHeadTail[1].next = pivot;
      pivot.next = secondHeadTail[0];
      return new ListNode[]{firstHeadTail[0], secondHeadTail[1]};
    } else if (firstHeadTail[1] != null) {
      firstHeadTail[1].next = pivot;
      return new ListNode[]{firstHeadTail[0], pivot};
    } else {
      pivot.next = secondHeadTail[0];
      return new ListNode[]{pivot, secondHeadTail[1]};
    }
  } // merge

  //-------------------------------------------------------------------------------------

  /**
   * Partitions the given linked list. Takes O(n) time and O(1) space
   *
   * @param head head node of the linked list to be partitioned
   * @return array of 3 elements, 1. head of first half 2. Pivot node and 3. head of second half
   */
  public static ListNode[] partition(ListNode head) {
    ListNode pivot = head;
    ListNode node = head.next;
    pivot.next = null;

    ListNode firstHalfHead = null;
    ListNode secondHalfHead = null;

    while (node != null) {
      ListNode curr = node;
      node = node.next;
      if (curr.val <= pivot.val) {
        curr.next = firstHalfHead;
        firstHalfHead = curr;
      } else {
        curr.next = secondHalfHead;
        secondHalfHead = curr;
      }
    }
    return new ListNode[]{firstHalfHead, pivot, secondHalfHead};
  } // partition

} // QuickSortLinkedList

//=======================================================================================

class ListNode {
  ListNode next;
  int val;

  //-------------------------------------------------------------------------------------

  public ListNode(int data) {
    this.val = data;
  }

  //-------------------------------------------------------------------------------------

  public String toString() {
    StringBuilder sb = new StringBuilder();
    ListNode node = this;
    while (node != null) {
      sb.append(node.val + " ");
      node = node.next;
    }
    return sb.toString();
  } // toString

} // ListNode