python3合并两个有序列表 and 加一

全栈程序员-站长 • 2021年4月18日下午8:00 • 未分类 • 阅读 141

21.合并两个有序列表点此做题

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

常规思路：

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        new_list = ListNode(-1,None)
        head = new_list
        while l1 and l2:
            if l1.val<l2.val:
                new_list.next = l1
                new_list=new_list.next
                l1=l1.next
            else:
                new_list.next = l2
                new_list=new_list.next
                l2=l2.next
        if l1:
            new_list.next = l1
        if l2:
            new_list.next = l2
        return head.next

递归思路

if not l1: return l2  # 终止条件，直到两个链表都空
        if not l2: return l1
        if l1.val <= l2.val:  # 递归调用
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：

输入：digits = [0]
输出：[1]

思路1：字符串和整型相互转然后+1，思路简单，但是耗用内存

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        str1 = ''
        lst = []
        for i in digits:
            str1 += str(i)
        str1 = str(int(str1)+1)
        for i in str1:
            lst.append(int(i))
        return lst

思路2：直接操作；将最后一位加一，然后判断是否需要进位，以及考虑最坏情况

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
		addone = 0
        digits[-1] += 1
        for i in range(len(digits)-1,-1,-1):
            if addone == 1:
                digits[i] += addone
                addone = 0
            if digits[i] == 10:
                digits[i] = 0
                addone = 1
            else:
                return digits
        if digits[0] == 0:
            digits.insert(0, 1)
            return digits

思路3：

newlst = []
        while digits and digits[-1] == 9:
            digits.pop()
            newlst.append(0)
        if not digits:
            return [1] + newlst
        else:
            digits[-1] += 1
            return digits + newlst