<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>