算法题（三）

本文主要是介绍算法题（三），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、合并两个有序链表

解题思路：两个链表都是升序链表，要将其串成一个升序链表，则需要新建一个链表，每次都指向节点的最小值，要考虑链表越界的情况。时间复杂度O(m+n)，空间复杂度O(1)。

代码：

# 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]
        """
        flage1 = list1;flage2= list2
        newlist = ListNode()
        satrt = newlist
        while flage1 != None or flage2 != None:
            if flage1 == None:
                newlist.next = flage2
                break
            if flage2 == None :
                newlist.next = flage1
                break
            if flage1.val <= flage2.val:
                newlist.next = flage1
                flage1 = flage1.next
            else:
                newlist.next = flage2
                flage2 = flage2.next
            newlist = newlist.next
        return satrt.next

注意：此题可用递归法，也可以用循环法。

2、删除有序数组中的重复项

解题思路：这道题比较简单，但是letcode上很多解法是不符合题意的。题中明确提到，需要原地删除旧数组中的元素！如果不删除这道题就很简单，遍历一遍就可以找到结果，但是如果原地删除旧数组中的元素，将会导致索引变化。因此可以采用双指针的方式来记录删除前后的位置信息。时间复杂度O(n)，空间复杂度O(1)。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <2:
            return len(nums)
        l = 0
        f = 1
        while l!=f:
            if f> len(nums)-1:
                break
            if nums[f] == nums[l]:
                del nums[f]
            else:
                l+=1
                f+=1
        return len(nums)

3、移除元素

解题思路：与上一题类似，只需要用一个指针记录位置就可以，符合条件就删除，不符合条件指针就+1。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        p = 0
        while p < len(nums):
            if nums[p] ==val:
                del nums[p]
            else:
                p += 1
        return len(nums)

这篇关于算法题（三）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！