program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

type
    TNode = ^SingleList;
    TNodePointer = ^TNode;

    SingleList = Record
        data: integer;
        next: TNode;
    End;

procedure push(var Header: TNode; Data: integer);

var
    NewNode: TNode;

begin
    new(NewNode);
    NewNode^.data := Data;
    NewNode^.next := Header^.next;
    Header^.next := newNode;
end;

procedure printList(Node: TNode);

begin
    while (Node <> nil ) do
    begin
        write(Node^.data, ' ');
        Node := Node^.next;
    end;
    writeln;
end;

function getTail(Node: TNode): TNode;

begin
    while (Node <> nil) and (Node^.next <> nil) do
        Node := Node^.next;
    Result := Node;

end;

// Partitions the list taking the last element as the pivot
function partition(head: TNode; fin: TNode;
                       var newHead: TNode;
                       var newEnd: TNode): TNode;

var
    pivot: TNode;
    prev: TNode;
    cur: TNode;
    tail: TNode;
    tmp: TNode;


begin
    pivot := fin;
    prev := nil;
    cur := head;
    tail := pivot;

    // During partition, both the head and end of the list
    // might change which is updated in the newHead and
    // newEnd variables
    while (cur <> pivot) do
    begin
        if (cur^.data < pivot^.data) then
        begin
            // First node that has a value less than the
            // pivot - becomes the new head
            if (newHead = nil) then
                newHead := cur;

            prev := cur;
            cur := cur^.next;
        end
        else // If cur node is greater than pivot
        begin
            // Move cur node to next of tail, and change
            // tail
            if (prev <> nil) then
                prev^.next := cur^.next;
            tmp := cur^.next;
            cur^.next := nil;
            tail^.next := cur;
            tail := cur;
            cur := tmp;
        end;
    end;

    // If the pivot data is the smallest element in the
    // current list, pivot becomes the head
    if (newHead = nil) then
        newHead := pivot;

    // Update newEnd to the current last node
    newEnd := tail;

    // Return the pivot node
    Result := pivot;
end;

// here the sorting happens exclusive of the end node
function quickSortRecur(head: TNode; fin: TNode): TNode;

var
    newHead: TNode;
    newEnd: TNode;
    tmp: TNode;
    pivot: TNode;



begin
    // base condition
    if ((not (head <> nil)) or (head = fin)) then
        Result := head
    else
    begin
        newHead := nil;
        newEnd := nil;

    // Partition the list, newHead and newEnd will be
    // updated by the partition function
        pivot := partition(head, fin, newHead, newEnd);

    // If pivot is the smallest element - no need to recur
    // for the left part.
        if (newHead <> pivot) then
        begin
            // Set the node before the pivot node as nullptr
            tmp := newHead;
            while (tmp^.next <> pivot) do
                tmp := tmp^.next;
            tmp^.next := nil;

            // Recur for the list before pivot
            newHead := quickSortRecur(newHead, tmp);

            // Change next of last node of the left half to
            // pivot
            tmp := getTail(newHead);
            tmp^.next := pivot;
        end;

    // Recur for the list after the pivot element
    pivot^.next := quickSortRecur(pivot^.next, newEnd);

    Result := newHead;
    end;
end;

procedure quickSort(var headRef: TNode);

var
    Tail: TNode;

begin
    Tail := getTail(headRef);
    headRef := quickSortRecur(headRef, Tail);
end;

var
    Header: TNode;

begin
    new(Header);
    Header^.next := nil;

    push(Header, 5);
  {  push(Header, 20);
    push(Header, 4);
    push(Header, 3);
    push(Header, 30);
    push(Header, 7);
    push(Header, 4);
    push(Header, 34);
    push(Header, 1);  }
    writeln('Linked List before sorting');
    printList(Header^.next);
    quickSort(Header^.next);
    writeln('Linked List after sorting');
    printList(Header^.next);
    Readln;
end.