LeetCode——合并两个有序链表
2020-01-17 本文已影响0人
Minority
题目描述
将两个有序链表合并为一个新的有序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
注意:看题时一定要注意审题......。初始的两个链表和最后合成的链表都是有序的。纪念一下沙雕的自己,不看题导致提交错误了好几次。
一、CPP
解题思路:这个题比较简单,思路也和两数相加差不多,就是比较两个链表的值后使用尾插法插入新的链表。
时间复杂度:O(n)
/**
* 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* head = new ListNode(0);
ListNode* p = head;
while(l1 && l2)
{
if(l2->val >= l1->val)
{
ListNode* r = new ListNode(l1->val);
p->next = r;
p = r;
l1 = l1->next;
}
else
{
ListNode* r = new ListNode(l2->val);
p->next = r;
p = r;
l2 = l2->next;
}
}
while(l1)
{
ListNode* r = new ListNode(l1->val);
p->next = r;
p = r;
l1 = l1->next;
}
while(l2)
{
ListNode* r = new ListNode(l2->val);
p->next = r;
p = r;
l2 = l2->next;
}
return head->next;
}
};
二、Java
与CPP语法差别总结:
- Java没有指针,一切皆对象,所以创建链表节点时会有不同。Java是类定义的链表节点,CPP是结构体定义的链表节点。
- Java定义的是链表类,类成员使用
"."
访问,CPP使用是结构体,创建的是指针类型的节点,指针类型的节点访问其成员变量时必须用"p->val"
,其相当于(*p).val
。 - 判断链表为空时,由于CPP使用的是指针,所以可以直接写出
while(l1)
,而Java没有指针的概念,所以必须使用while(l1!=null)
来判断。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode p = head;
while(l1!=null && l2!=null)
{
if(l2.val >= l1.val)
{
ListNode r = new ListNode(l1.val);
p.next = r;
p = r;
l1 = l1.next;
}
else
{
ListNode r = new ListNode(l2.val);
p.next = r;
p = r;
l2 = l2.next;
}
}
while(l1!=null)
{
ListNode r = new ListNode(l1.val);
p.next = r;
p = r;
l1 = l1.next;
}
while(l2!=null)
{
ListNode r = new ListNode(l2.val);
p.next = r;
p = r;
l2 = l2.next;
}
return head.next;
}
}
三、Python
与前两者语法细节差别:
- python 创建对象时不用使用new
- 在python中,
&&
为and
- 注意while和if不用加()
# 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
"""
head = ListNode(0)
p =head
while l1!=None and l2!=None:
if l1.val<=l2.val:
r = ListNode(l1.val)
p.next = r
p = r
l1 = l1.next
else:
r = ListNode(l2.val)
p.next = r
p = r
l2 = l2.next
while l1!=None:
r = ListNode(l1.val)
p.next = r
p = r
l1 = l1.next
while l2!=None:
r = ListNode(l2.val)
p.next = r
p = r
l2 = l2.next
return head.next