<script>
var head;
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
function newNode(key)
{
return new Node(key);
}
function sort()
{
var Ahead = new Node(0),
Dhead = new Node(0);
splitList(Ahead, Dhead);
Ahead = Ahead.next;
Dhead = Dhead.next;
Dhead = reverseList(Dhead);
head = mergeList(Ahead, Dhead);
}
function reverseList(Dhead)
{
var current = Dhead;
var prev = null;
var next;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
Dhead = prev;
return Dhead;
}
function printList()
{
var temp = head;
while (temp != null)
{
document.write(temp.data + " ");
temp = temp.next;
}
document.write();
}
function mergeList(head1, head2)
{
if (head1 == null)
return head2;
if (head2 == null)
return head1;
var temp = null;
if (head1.data < head2.data)
{
temp = head1;
head1.next = mergeList(head1.next, head2);
}
else
{
temp = head2;
head2.next = mergeList(head1, head2.next);
}
return temp;
}
function splitList(Ahead, Dhead)
{
var ascn = Ahead;
var dscn = Dhead;
var curr = head;
while (curr != null)
{
ascn.next = curr;
ascn = ascn.next;
curr = curr.next;
if (curr != null)
{
dscn.next = curr;
dscn = dscn.next;
curr = curr.next;
}
}
ascn.next = null;
dscn.next = null;
}
head = newNode(10);
head.next = newNode(40);
head.next.next = newNode(53);
head.next.next.next =
newNode(30);
head.next.next.next.next =
newNode(67);
head.next.next.next.next.next =
newNode(12);
head.next.next.next.next.next.next =
newNode(89);
document.write("Given linked list<br/>");
printList();
sort();
document.write("<br/>Sorted linked list<br/>");
printList();
</script>
