【题目】
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:->->, ->->
输出:->->->->->
【思路】
本题较为简单,遍历两个链表,比较元素大小,将较小的元素依次插入新的链表中。注意的是,退出循环时,有一个链表还没有遍历完所有元素。
【代码】
python版本
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l = ListNode()
head = l
node1 = l1
node2 = l2
while node1 and node2:
l.next = ListNode()
l = l.next
if node1.val <= node2.val:
l.val = node1.val
node1 = node1.next
else:
l.val = node2.val
node2 = node2.next
while node1:
l.next = ListNode()
l = l.next
l.val = node1.val
node1 = node1.next
while node2:
l.next = ListNode()
l = l.next
l.val = node2.val
node2 = node2.next
return head.next
C++版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* node1 = l1;
ListNode* node2 = l2;
ListNode* l = new ListNode();
ListNode* head = l;
while(node1 && node2){
l->next = new ListNode();
l = l->next;
if(node1->val <= node2->val){
l->val = node1->val;
node1 = node1->next;
}else{
l->val = node2->val;
node2 = node2->next;
}
}
while(node1){
l->next = new ListNode();
l = l->next;
l->val = node1->val;
node1 = node1->next;
}
while(node2){
l->next = new ListNode();
l = l->next;
l->val = node2->val;
node2 = node2->next;
}
return head->next;
}
};