Description
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.
Difficulty
Solution
Idea
由于两个列表已排好序，因此可以设置两个下标i，j，分别指向l1和l2的首节点，再从头到尾分别比较两个列表当前下标对应的元素的大小关系，接着存到新列表（注意，这里题干要求“return it as a new list”）。需要留意两个列表的长度不一致的情况。
python
1 # Definition for singly-linked list. 2 # class ListNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 class Solution(object): 8 def mergeTwoLists(self, l1, l2): 9 """10 :type l1: ListNode11 :type l2: ListNode12 :rtype: ListNode13 """14 if l1 == None and l2 == None:15 return None16 17 result = ListNode(-1)18 result_cur = result19 20 ptr1 = l121 ptr2 = l222 23 while ptr1 and ptr2:24 if ptr1.val <= ptr2.val:25 new_node = ListNode(ptr1.val)26 result_cur.next = new_node27 ptr1 = ptr1.next28 else:29 new_node = ListNode(ptr2.val)30 result_cur.next = new_node31 ptr2 = ptr2.next32 33 result_cur = result_cur.next34 35 while ptr1:36 new_node = ListNode(ptr1.val)37 result_cur.next = new_node38 result_cur = result_cur.next39 ptr1 = ptr1.next40 41 while ptr2:42 new_node = ListNode(ptr2.val)43 result_cur.next = new_node44 result_cur = result_cur.next45 ptr2 = ptr2.next46 47 return result.next
cpp
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 && l2==NULL)13 {14 return NULL;15 }16 ListNode* ptr1 = l1;17 ListNode* ptr2 = l2;18 ListNode* result = new ListNode(-1);19 ListNode* result_cur = result;20 21 while (ptr1 && ptr2)22 {23 if (ptr1->val <= ptr2->val)24 {25 result_cur->next = new ListNode(ptr1->val);;26 ptr1 = ptr1->next;27 }else28 {29 result_cur->next = new ListNode(ptr2->val);30 ptr2 = ptr2->next;31 }32 result_cur = result_cur->next;33 }34 while (ptr1)35 {36 result_cur->next = new ListNode(ptr1->val);37 result_cur = result_cur->next;38 ptr1 = ptr1->next;39 }40 while (ptr2)41 {42 result_cur->next = new ListNode(ptr2->val);;43 result_cur = result_cur->next;44 ptr2 = ptr2->next;45 }46 47 return result->next;48 }49 };