Merge Two Sorted Lists

 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         
13         ListNode *l3 = new ListNode(0);
14         ListNode *p1 = l1;
15         ListNode *p2 = l2;
16         ListNode *p3 = l3;
17         
18         while(p1 != NULL && p2 != NULL)
19         {
20             ListNode *node = new ListNode(0);
21             if(p1->val <= p2->val)
22             {
23                 node->val = p1->val;
24                 p1 = p1->next;
25             }
26             else
27             {
28                 node->val = p2->val;
29                 p2 = p2->next;
30             }
31             p3->next = node;
32             p3 = p3->next;
33             node = NULL;
34         }
35         
36         while(p1 != NULL)
37         {
38             ListNode *node = new ListNode(p1->val);
39             p3->next = node;
40             p3 = p3->next;
41             node = NULL;
42             p1 = p1->next;
43         }
44         
45         while(p2 != NULL)
46         {
47             ListNode *node = new ListNode(p2->val);
48             p3->next = node;
49             p3 = p3->next;
50             node = NULL;
51             p2 = p2->next;
52         }
53         
54         ListNode *del = l3;
55         l3 = l3->next;
56         delete del;
57         
58         return l3;
59     }
60 };