专栏首页Bingo的深度学习杂货店Leetcode【24、109、328、455、725】

Leetcode【24、109、328、455、725】

问题描述:【Linked List、Recursion】24. Swap Nodes in Pairs
解题思路:

这道题是给一个链表,相邻结点数值两两进行交换,要求不修改结点值且只能操作链表本身。

方法1:三指针完成交换

链表中一般涉及两个结点交换的操作,基本上需要相邻的三个指针 pre1,pre2,cur 完成三次交换操作,然后再移动三个指针到下一个正确的位置。 因此,我们只需要循环 cur 的位置,往后一直遍历直到链表为空为止。

在这道题中,因为是两两交换,所以方便的解法就是建立一个空给点 node,作为链表的头结点 head,最后返回的 head.next 就是答案。

注意在交换的过程中,每次交换的三个操作要保证链表不能断。

时间复杂度 O(n),空间复杂度 O(1)。

Python3 实现:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head == None or head.next == None: return head
        node = ListNode(-1)  # 头部插入一个空结点
        node.next = head
        head = node
        # 三指针法
        pre2, pre1, cur = head, head.next, head.next.next
        while cur:
            pre2.next = cur  # 交换
            pre1.next = cur.next
            cur.next = pre1
            pre2 = pre1  # 修改
            pre1 = pre1.next
            if pre1 == None: break  # 防止pre1.next为空
            cur = pre1.next
        return head.next

方法2:递归

这道题实际上还可以使用递归(只不过不太好想,看了别人的代码才恍然大悟)。

1、函数的返回值:交换后的链表的头结点 head。 2、递归函数做了什么:假设 1->2->3->4->5->...,递归函数完成了 3->4->5... 的交换 swapPairs(head.next.next),并返回了指向 4 的 head,因此需要建一个 second 指向 2,然后将 head.next 指向递归函数的返回值,并将 second 作为头结点 head,最后返回 second3、递归出口:如果链表为空或者 head.next 为空,就之间返回 head。

总之,你不用去想递归函数 swapPairs() 后面的交换是怎么完成的,只需要知道它能够完成交换即可(或许这就是递归的精髓吧)。

时间复杂度 O(n),空间复杂度 O(1)。

Python3 实现:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:  # 递归出口
            return head
        second = head.next
        head.next = self.swapPairs(head.next.next)
        second.next = head
        return second

问题描述:【Linked List、Tree】109. Convert Sorted List to Binary Search Tree
解题思路:

这道题是给一个有序链表,将其转化为高度平衡的二叉搜索树。

要将有序链表转化为高度平衡的二叉搜索树,就需要从链表的中间断开,然后对于左右链表就行递归调用即可。具体细节:

1、链表查找中间点可以通过快慢指针来操作。 2、找到中点后,要以中点的值建立一个树的根结点,再把原链表断开,分为前后两个链表,都不能包含原中结点,然后再分别对这两个链表递归调用原函数,分别连上左右子结点即可。

时间复杂度为 O(nlogn),空间复杂度为 O(1)。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if head == None:
            return None
        if head.next == None:
            return TreeNode(head.val)
        pre = None  # 记录 slow 的前一个结点,便于断开左右链表
        slow = fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None # 从中间断开
        node = TreeNode(slow.val)
        node.left = self.sortedListToBST(head) # [head, slow-1] 左区间
        node.right = self.sortedListToBST(slow.next)  # [slow+1,] 右区间
        return node

问题描述:【Linked List】328. Odd Even Linked List
解题思路:

这道题是给一个链表,将奇数位置的数按位置顺序排在链表前面,偶数位置的数按位置顺序排在链表后面。要求空间复杂度 O(1),时间复杂度 O(n)。

设置三个指针,一个指向奇数尾部的指针 p,一个指向当前结点 cur,一个指向当前结点的前一个结点 pre。遍历 cur 的过程中交换三个指针的指向,然后再移动它们到下一个正确的位置即可。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if head == None: return None
        p = pre = head   # p: 奇数尾结点, pre: cur的前一个结点
        cur = head.next  # 当前结点
        while cur:
            pre = pre.next
            cur = cur.next
            if cur == None:  # 防止后面交换的时候cur没有next域
                break
            pre.next = cur.next # 交换
            cur.next = p.next
            p.next = cur
            p = p.next  # 下一次交换做准备
            cur = pre.next
        return head

问题描述:【Linked List】445. Add Two Numbers II
解题思路:

这道题是给两个链表,将两个链表相加。

使用了一种简单的做法,就是将两个链表的值保存在 list 中,然后反向遍历 list,利用头插法构造新链表,将每次计算的各个位的结果保存在新链表中即可。这样时间复杂度和空间复杂度均为 O(n),代码如下。

实际上这道题还可以使用链表反转的思想,将两链表反转,然后再求和。这样空间复杂度可以做到 O(1)。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        list1, list2 = [], []
        head1, head2 = l1, l2
        while head1:
            list1.append(head1.val)
            head1 = head1.next
        while head2:
            list2.append(head2.val)
            head2 = head2.next
        i, j, c = len(list1) - 1, len(list2) - 1, 0  # c:进位
        head = None
        while i >= 0 or j >= 0 or c == 1:
            add = c
            if i >= 0: add += list1[i]
            if j >= 0: add += list2[j]
            c = add // 10
            node = ListNode(add % 10)
            node.next = head  # 头插法
            head = node
            i, j = i - 1, j - 1 
        return head

问题描述:【Linked List】725. Split Linked List in Parts
解题思路:

这道题是给一个链表和整数 k,将链表划分成长度尽可能相等的 k 个连续部分,返回链表列表。

首先需要注意,链表列表是指一个列表,列表中每一项是一个链表。这道题根据链表的长度 size (先遍历一次链表)分为两种情况:

1、size <= k:每段链表只有一个值或者为 None。 2、size > k:通过 div, mod = divmod(size, k) 来计算每段链表中至少应该包含 div 个值,然后将 mod 平均分配到前面每一段链表中。

Python3 实现:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        cur = root
        size = 0  # 链表长度
        while cur:
            size += 1
            cur = cur.next
        ans = []  # 结果
        if size <= k:
            cur = root
            for i in range(k):
                if i < size:
                    ans.append(ListNode(cur.val))
                    cur = cur.next
                else:
                    ans.append(None)  # 空链表
        else:
            div, mod = divmod(size, k)
            for _ in range(k):  # 对于每一段
                head = cur = root  # head 构造每一段链表
                for _ in range(div - 1):  # 注意少循环一次,防止 cur.next 越界
                    cur = cur.next
                if mod > 0:  # 有余数,平均分配到前面每一段链表中
                    cur = cur.next
                    mod -= 1
                root = cur.next  # root 指向剩余的链表
                cur.next = None  # 截断
                ans.append(head) # 将每一段链表保存
        return ans

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python爬虫进阶必备 | 关于MD5 Hash 的案例分析与总结

    aHR0cHM6Ly9tLndjYmNoaW5hLmNvbS9sb2dpbi9vdGhlci1sb2dpbi5odG1s

    咸鱼学Python
  • SimpleDateFormat线程不安全示例及其解决方法

    我们可以用java.text.SimpleDateFormat类完成日期的转换和格式化操作,如:

    孟君
  • 「首席架构师推荐」数值分析软件列表

    原文:https://en.wikipedia.org/wiki/List_of_numerical-analysis_software

    首席架构师智库
  • 每30秒学会一个Python小技巧,GitHub星数4600+

    很多学习Python的朋友在项目实战中会遇到不少功能实现上的问题,有些问题并不是很难的问题,或者已经有了很好的方法来解决。当然,孰能生巧,当我们代码熟练了,自然...

    CDA数据分析师
  • Data Science | Pandas基础(三)-Timestamp

    在学习时间序列之前我们需要先了解一下datetime模块的基本使用,datetime模块不是pandas库中所包含的。

    咸鱼学Python
  • 自研测试框架ktest介绍(适用于UI和API)

    在自动化测试的过程中,测试框架是我们绕不过去的一个工具,无论你是不需要写代码直接改动数据生成脚本,还是你需要检查测试结果甚至持续集成,测试框架都在发挥它的作用。...

    测试开发社区
  • 【JS】370- 总结异步编程的六种方式

    众所周知 JavaScript 是 单线程工作,也就是只有一个脚本执行完成后才能执行下一个脚本,两个脚本不能同时执行,如果某个脚本耗时很长,后面的脚本都必须排队...

    pingan8787
  • 增强Jupyter Notebook的功能,这里有四个妙招

    Jupyter Notebook 是所有开发者共享工作的神器,它为共享 Notebooks 提供了一种便捷方式:结合文本、代码和图更快捷地将信息传达给受众。目前...

    CDA数据分析师
  • Data Science | Numpy基础(二)

    按照上篇文章,相信大家都安装好了Anaconda,有朋友在留言区留言希望出一篇关于Anaconda的使用教程,其实Anaconda的基本使用非常简单,基本无需教...

    咸鱼学Python
  • Python爬虫进阶必备 | 关于AES 的案例分析与总结

    可以看到这里 password、email 是加密的结果,_token 的值可以直接在页面里找到。

    咸鱼学Python

扫码关注云+社区

领取腾讯云代金券