CareerCup

My two pointer approach is O(n) time and O(1) space, but requires some preprocessing. First we create a sentinel head pointing to the first node. Then we create another fake node pointing to the first node of the second half.

For example, 1->3->5->2->4->6 becomes head->1->3->5->fake->2->4->6.

Now let p1 = head and p2 = fake. In each iteration, we let n1 & n2 be the next nodes of p1 & p2, respectively. We compare the values of n1 & n2. If n1 <= n2, we simply increment p1. Otherwise, we try to rip n2 out and insert it between p1 and n1, and then again increment p1. So we are actually incrementing p1 in both cases.

The while loop ends when either p1 or p2 has reached the end. That happens when p1->next (n1) is same as p2, or when p2->next (n2) is null.

while(true) {
	n1 = p1->next;
	n2 = p2->next;
	if(n1 == p2 || n2 == null)
		break;
	if(n1 <= n2) {
		p1 = p1->next;
	} else {
		p2->next = n2->next;
		p1->next = n2;
		n2->next = n1;
		p1 = p1->next;
	}
}
p1->next = p2->next

Use the two pointer approach. Keep one pointer at the beginning of the first half and one at the beginning of the second half. Compare the values of the two pointers and make the required insertions. O(n) time, O(1) space

total complexity with above approach will be O(n^2) which is not advisable. This can be done for any list, we are not taking advantage of both are sorted.

two steps:
(1)find the boundary of the two independently sorted list.
(2)change the pointer field of the node whose value is smaller.
Following is C code:

Node* sort(Node* head)
{
    if(head == NULL) return head;

    //step 1: find the boundary of the two independently sorted list
    Node *p = head, *left = head, *right;
    while(p->next != NULL && p->value <= p->next->value){
        p = p->next;
    }
    if(p->next == NULL) return head;
    else{
        right = p->next;
        p->next = NULL;
    } 

    //step 2: change the pointer field of the node whose value is smaller
    head = left->value > right->value ? right : left;
    while(left != NULL && right != NULL){
        if(left->value > right->value){
            p = right->next;
            right->next = left;
            right = p;
        }
        else{
            p = left->next;
            left->next = right;
            left = p;
        }
    }

    return head;
}

Sorry for the above code. It should be like this:

Node* sort(Node* head)
{
    if(head == NULL) return head;

    //step 1: find the boundary of the two independently sorted list
    Node *p = head, *q;

    while(p->next != NULL && p->value <= p->next->value){
        p = p->next;
    }
    if(p->next == NULL) return head;
    else{
        q = p->next;
        p->next = NULL;
    } 

    //step 2: merge list
    if(head->value > q->value){
        p = q;
        q = head;
        head = p;
    }
    
    Node* t = head;
    for(p = p->next; p != NULL && q != NULL; t = t->next;){
        if(p->value > q->value){
            t->next = q;
            q = q->next;
        }
        else{
            t->next = p;
            p = p->next;
        }
    }
    if(p != NULL) t->next = p;
    else t->next = q;

    return head;
}

how about just exchange val between nodes, whereas keep the next ptr stable? that will make the code much easier.