leetcode: Merge Two Sorted Lists

leetcode Merge Two Sorted Lists Problem Description:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

leetcode Merge Two Sorted Lists Solution and Precautions:

This problem tests your ability to deal with pointers. Nothing special, just follow the normal merge sort algorithm, and take good care of all those pointers. You might need several different pointers like the new head pointer and another pointer to the tail of the new list since you need it to append the remaining nodes. Always try to draw the pointers out and it will be much easier for you to write out the correct code. The following is the accepted code.

class Solution {
	ListNode *Merge(ListNode *p1, ListNode *p2)
		if (NULL == p1) return p2;
		if (NULL == p2) return p1;

		ListNode *head(NULL), *tail(NULL);

		ListNode **smaller = &p2;
		if (p1->val < p2->val) smaller = &p1;

		head = tail = *smaller;
		(*smaller) = (*smaller)->;next;
		tail->next = NULL;

		while (p1 && p2) {
			smaller = &p2;
			if (p1->val < p2->val) smaller = &p1;

			tail->next = (*smaller);
			tail = tail->next;
			(*smaller) = (*smaller)->next;
			tail->next = NULL;

		if (p1) tail->next = p1;
		if (p2) tail->next = p2;
		return head;

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
		return Merge(l1, l2);

leetcode Merge Two Sorted Lists Tips and Remarks:

My suggestion to make the coding less error-prone would be that try to use helper pointers like temporary pointers as many as you want, just make the code working, after that, try to refactor the code and eliminate those unnecessary code statements, my above code is just a refactored version from a longer piece of code (there are 20 lines more in that longer code).

Written on April 27, 2013