leetCode 21. Merge Two Sorted Lists 合并链表

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.

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

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

代码如下：

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { 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;         return newListHead->next;     } };

2016-08-06 01:40:31