【LeetCode OJ】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 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) : val(x), next(NULL) {}
 5     
 6 };
 7 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
 8 {
 9     if (l2 == NULL)
10         return l1;
11     if (l1 == NULL)
12         return l2;
13     ListNode  *r, *head;
14     head = NULL;
15     if (l1->val <= l2->val)  //哪个链表的第一个节点小就把头指针指向哪个节点
16     {
17         head = l1;
18         l1 = l1->next;
19     }
20     else
21     {
22         head = l2;
23         l2 = l2->next;
24     }
25     r = head;
26     while (l1&&l2)    //比较大小
27     {
28         if (l1->val <= l2->val)
29         {
30             r->next = l1;
31             l1 = l1->next;
32         }
33         else
34         {
35             r->next = l2;
36             l2 = l2->next;
37         }
38         r = r->next;
39     }
40     if (l1 == NULL)   //l1为空，直接连接l2
41     {
42         r->next = l2;
43     }
44     if (l2 == NULL)  //l2为空，直接连接l1
45     {
46         r->next = l1;
47     }
48     return head;
49 }