* Definition for singly-linked list.
* public class ListNode {
* ListNode(int x) { val = x; }
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
while (curNode != null) {
ListNode left = null, right = null, tail = null, dummy = null;
for (int step = 1; step < len; step *= 2) {
while (curNode != null) {
right = split(left, step);
curNode = split(right, step);
tail = merge(left, right, tail);
// Split a linked list into half, where the first half contains n nodes (or all nodes)
// Return the head of the second half list (or null)
public ListNode split(ListNode head, int n) {
for (int i = 1; head != null && i < n; i++) {
ListNode second = head.next;
// Merge two sorted linked list l1 and l2
// Append the result to list node tail
// Return the tail of merge sorted list
public ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
while (l1 != null && l2 != null) {
curNode.next = l1 == null ? l2 : l1;
while (curNode.next != null) {