Leetcode Sort List problem solution

In this Leetcode Sort List problem solution we have Given the head of a linked list, return the list after sorting it in ascending order.

Problem solution in Python.

def mergeTwoLists(self, l1, l2):
        dummy = h = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                h.next = l1
                l1 = l1.next
            else:
                h.next = l2
                l2 = l2.next
            h = h.next
        h.next = l1 or l2
        return dummy.next

    def sortList(self, head):
        if not head or not head.next:
            return head

        pre = slow = fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None

        l1 = self.sortList(head)
        l2 = self.sortList(slow)
        return self.mergeTwoLists(l1, l2)

Problem solution in Java.

class Solution {
    public ListNode sortList(ListNode head) {
        return helper(head);
    }
    
    public ListNode helper(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = new ListNode(0);
        prev.next = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            prev = prev.next;
        }
        prev.next = null;
        ListNode head2 = slow;
        head = helper(head);
        head2 = helper(head2);
        return merge(head, head2);
    }

    public ListNode merge(ListNode head1, ListNode head2){
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        ListNode dummy = new ListNode(0);
        dummy.next = head1;
        ListNode curr1 = dummy;
        ListNode curr2 = head2;
        while(curr1.next != null && curr2 != null){
            if(curr1.next.val < curr2.val){
                curr1 = curr1.next;
            }else{
                ListNode next1 = curr1.next;
                ListNode next2 = curr2.next;
                curr1.next = curr2;
                curr2.next = next1;  
                curr2 = next2;
            } 
        }
        if(curr2 != null){
            curr1.next = curr2;
        }
        return dummy.next;
    }
}

Problem solution in C++.

public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }

        ListNode *slow = head, *fast = head, *pre = head;
        while(fast != nullptr && fast->next != nullptr){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;

        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);

        ListNode* newHead = this->merge(left, right);
        return newHead;
    }
private:
    ListNode* merge(ListNode* left, ListNode* right){
        ListNode newHead(-1);
        ListNode* p = &newHead;
        while(left != nullptr && right != nullptr){
            if(left -> val < right->val){
                p->next = left;
                left = left->next;
            }else{
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
        if(left != nullptr){
            p->next = left;
        }else if(right != nullptr){
            p->next = right;
        }
        return newHead.next;
    }

Problem solution in C.

static struct ListNode *merge(struct ListNode*a, struct ListNode*b) {

	struct ListNode head, *tail;
	tail = &head;
	while (a && b) {
		if ((a->val <= b->val) ) {
			tail->next = a;
			a = a->next;
		} else {
			tail->next = b;
			b = b->next;
		}
		tail = tail->next;
	}
	tail->next = a ? : b;
	return head.next;
}
#define MAX_LIST_LENGTH_BITS 31

struct ListNode* sortList(struct ListNode* head) {
    struct ListNode *part[MAX_LIST_LENGTH_BITS + 1];
	int lev;
	int max_lev = 0;
	struct ListNode *bnode;

	if (head == NULL)
		return head;
	memset(part, 0, sizeof(part));
	bnode = head;

	while (bnode) {
		struct ListNode *cur = bnode;
		bnode = bnode->next;
		cur->next = NULL;

		for (lev = 0; part[lev]; lev++) {
			cur = merge(part[lev], cur);
			part[lev] = NULL;
		}
		if (lev > max_lev) {
			if ((lev >= MAX_LIST_LENGTH_BITS)) {
				lev--;
			}
			max_lev = lev;
		}
		part[lev] = cur;
	}

	for (lev = 0; lev < max_lev; lev++)
		if (part[lev])
			bnode = merge(part[lev], bnode);

	bnode = merge(part[max_lev], bnode);

	return bnode;
}