[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.

维护一个新的链表，用两个指针指向两个链表，类似merge sot的比较。

 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         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14         if (l1 == NULL)
15             return l2;
16             
17         if (l2 == NULL)
18             return l1;
19             
20         ListNode *p = l1;
21         ListNode *q = l2;
22         ListNode *head = NULL;
23         ListNode *curNode = NULL;
24         
25         while(p && q)
26         {
27             if (head == NULL)
28             {
29                 if (p->val < q->val)
30                 {
31                     head = curNode = p;
32                     p = p->next;
33                     curNode->next = NULL;
34                 }
35                 else
36                 {
37                     head = curNode = q;
38                     q = q->next;
39                     curNode->next = NULL;
40                 }
41             }
42             else
43             {
44                 if (p->val < q->val)
45                 {
46                     curNode->next = p;
47                     curNode = p;
48                     p = p->next;
49                     curNode->next = NULL;
50                 }
51                 else
52                 {
53                     curNode->next = q;
54                     curNode = q;
55                     q = q->next;
56                     curNode->next = NULL;
57                 }
58             }
59         }
60         
61         if (p)
62             curNode->next = p;
63         else if (q)
64             curNode->next = q;
65             
66         return head;       
67     }
68 };