21. Merge Two Sorted Lists

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.

题目大意：合并两个有序的链表

思路：通过比较两个链表的节点大小，采用尾插法建立链表。

代码如下：

/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:ListNode*mergeTwoLists(ListNode*l1,ListNode*l2){ListNode*newListHead,*newListNode,*newListTail;newListHead=(ListNode*)malloc(sizeof(ListNode));newListTail=newListHead;while((NULL!=l1)&&(NULL!=l2)){if(l1->val<=l2->val){newListNode=(ListNode*)malloc(sizeof(ListNode));newListNode->val=l1->val;newListTail->next=newListNode;newListTail=newListNode;l1=l1->next;}else{newListNode=(ListNode*)malloc(sizeof(ListNode));newListNode->val=l2->val;newListTail->next=newListNode;newListTail=newListNode;l2=l2->next;}}if(NULL!=l1){while(l1){newListNode=(ListNode*)malloc(sizeof(ListNode));newListNode->val=l1->val;newListTail->next=newListNode;newListTail=newListNode;l1=l1->next;}}if(NULL!=l2){while(l2){newListNode=(ListNode*)malloc(sizeof(ListNode));newListNode->val=l2->val;newListTail->next=newListNode;newListTail=newListNode;l2=l2->next;}}newListTail->next=NULL;returnnewListHead->next;}};

2016-08-06 01:40:31