目录
题目描述:
解题思路:
C++代码:
python代码:
题目描述:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路:
一句话,两个指针遍历链表,尾插法更新新链表。
1) 定两个指针p1和p2,分别指向两个链表;
2)p1->val <= p2->val,则将p1值利用尾插法,插入合并后的新表中,然后p1 = p1->next;
3)反之,则将p2值利用尾插法,插入合并后的新表中,然后p2 = p2->next;
4)当任意一个表遍历完后,把另一个表的其他值直接插入新表中。
C++代码:
执行用时:8 ms, 在所有 C++ 提交中击败了64.93%的用户
内存消耗:14.7 MB, 在所有 C++ 提交中击败了5.16%的用户
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr && list2 == nullptr) return nullptr;
if (list1 == nullptr) return list2;
if (list2 == nullptr) return list1;
ListNode* p_dummy = new ListNode(0); // 最终结果的头节点,返回的是p->next
ListNode* p_tail = p_dummy; // 尾插法,当前正在处理的尾节点。
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 && p2)
{
ListNode* p_new;
if (p1->val <= p2->val)
{
p_new = new ListNode(p1->val);
p1 = p1->next; // 插入P1,则p1后移
}
else
{
p_new = new ListNode(p2->val);
p2 = p2->next; // 插入P2,则p2后移
}
p_tail->next = p_new; // 插入
p_tail = p_new; // 更新尾部
}
while (p1)
{
ListNode* p_new = new ListNode(p1->val);
p_tail->next = p_new;
p_tail = p_new;
p1 = p1->next;
}
while (p2)
{
ListNode* p_new = new ListNode(p2->val);
p_tail->next = p_new;
p_tail = p_new;
p2 = p2->next;
}
return p_dummy->next;
}
};
python代码:
执行用时:20 ms, 在所有 Python 提交中击败了85.04%的用户
内存消耗:13.2 MB, 在所有 Python 提交中击败了32.97%的用户
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if list1 is None and list2 is None: return None
if list1 is None: return list2
if list2 is None: return list1
p_dummpy = ListNode(0)
p_tail = p_dummpy
p1 = list1
p2 = list2
while p1 and p2:
if p1.val <= p2.val:
p_new = ListNode(p1.val)
p_tail.next = p_new
p_tail = p_new # 更新尾部
p1 = p1.next
else:
p_new = ListNode(p2.val)
p_tail.next = p_new
p_tail = p_new # 更新尾部
p2 = p2.next
while p1:
p_new = ListNode(p1.val)
p_tail.next = p_new
p_tail = p_new # 更新尾部
p1 = p1.next
while p2:
p_new = ListNode(p2.val)
p_tail.next = p_new
p_tail = p_new # 更新尾部
p2 = p2.next
return p_dummpy.next