LeetCode Q148: Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Solution:
Using merge sort.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* merge(ListNode* head1, ListNode* head2){
	ListNode* p1=head1;
	ListNode* p2=head2;
	ListNode* newHead=NULL;
	ListNode* p=NULL;
	while(p1!=NULL&&p2!=NULL){
	ListNode* tmp=NULL;
	if(p1->val<p2->val){
	tmp=p1;
	p1=p1->next;
	}else{
	tmp=p2;
	p2=p2->next;
	}
	if(newHead==NULL){
	newHead=tmp;
	p=tmp;
	}else{
	p->next=tmp;
	p=tmp;
	}
	}
	if(p1==NULL)
	p->next=p2;
	else if(p2==NULL)
	p->next=p1;
	return newHead;
	}
	ListNode* sortList(ListNode* head){
	if(head==NULL||head->next==NULL)
	return head;
	ListNode* head1=head;
	ListNode* head2=head->next;
	while(head2 && head2->next){
	head1=head1->next;
	head2=head2->next->next;
	}
	head2=head1->next;
	head1->next=NULL;
	head1=head;
	ListNode* newHead1=sortList(head1);
	ListNode* newHead2=sortList(head2);
	head=merge(newHead1, newHead2);
	return head;
	}
	};

view raw Q148SortList.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* merge(ListNode* head1, ListNode* head2){
	ListNode* head = new ListNode(1);
	ListNode* p;
	if(head1==NULL||head2==NULL)
	return head1==NULL? head2:head1;
	while(head1!=NULL||head2!=NULL){
	if(head1==NULL||head2==NULL){
	p->next = head1==NULL? head2:head1;
	break;
	}
	ListNode* curNode;
	if(head1->val<head2->val){
	curNode=head1;
	head1=head1->next;
	}else{
	curNode=head2;
	head2=head2->next;
	}
	if(head->next==NULL){
	head->next=curNode;
	p=curNode;
	p->next=NULL;
	}else{
	p->next=curNode;
	p=curNode;
	p->next=NULL;
	}
	}
	ListNode* tmp = head->next;
	delete head;
	return head->next;
	}
	ListNode* sortList(ListNode* head) {
	if(head->next==NULL)
	return head;
	ListNode* p0 = head;
	ListNode* p1 = head;
	while(p1->next!=NULL&&p1->next->next!=NULL){
	p0 = p0->next;
	p1 = p1->next->next;
	}
	p1 = p0->next;
	p0->next=NULL;
	p0 = head;
	p0 = sortList(p0);
	p1 = sortList(p1);
	head = merge(p0, p1);
	return head;
	}
	};

view raw Q148Rnd2.cpp hosted with ❤ by GitHub