leetcode 题解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.

说明：有序链表归并（从小到大）

1）此链表无头节点

实现：

方法一：非递归

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12         ListNode *la=l1,*lb=l2;
13         ListNode *q=NULL,*p=NULL;
14         if(la==NULL) return l2;
15         if(lb==NULL) return l1;
16         //此单链表无头结点，若有头结点，可直接p=head节点即可，无需下面的if...else...
17         if((la->val) < (lb->val))
18             {
19                 p=la;
20                 la=la->next;
21             }
22         else
23             {
24                 p=lb;
25                 lb=lb->next;
26             }
27         q=p;
28         while(la&&lb)
29         {
30             if((la->val) < (lb->val))
31             {
32                 p->next=la;
33                 p=la;
34                 la=la->next;
35             }
36             else
37             {
38                 p->next=lb;
39                 p=lb;
40                 lb=lb->next;
41             }
42         }
43         p->next=la?la:lb;
44         return q;
45     }
46 };

View Code

方法二：递归（紫红的泪大牛的代码，博客链接：http://www.cnblogs.com/codingmylife/archive/2012/09/27/2705286.html）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12         if (l1 == NULL) return l2;
13     if (l2 == NULL) return l1;
14     
15     ListNode *ret = NULL;
16     
17     if (l1->val < l2->val)
18     {
19         ret = l1;
20         ret->next = mergeTwoLists(l1->next, l2);
21     }
22     else
23     {
24         ret = l2;
25         ret->next = mergeTwoLists(l1, l2->next);
26     }
27     
28     return ret;
29     }
30 };

View Code