专栏首页Bingo的深度学习杂货店Leetcode【61、82、83、142、143、1171】

Leetcode【61、82、83、142、143、1171】

问题描述:【Linked List】61. Rotate List
解题思路:

这道题是给一个链表,旋转链表,将链表每个结点向右移动 k 个位置。

1、先计算链表长度 size,k = k % size,如果 k % size == 0,则不用移动,直接返回 head; 2、否则,需要将前 size - k 个结点移动到后面。因此只需要循环 size - k 次,找到新链表头部,然后进行指针的交换。最后返回新链表头即可。

注意:这道题虽然是旋转链表,但是实际上并没有真正的进行结点的移动,只是进行了指针的交换。

时间复杂度为 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 rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return head
        cur, size = head, 1
        while cur.next:  # cur 结束后记录链表尾
            size += 1
            cur = cur.next
        k = k % size
        if k == 0:  # 不用旋转
            return head
        i, pre, newhead = 0, None, head  # pre:newhead的前一个, newhead:新头部
        while i < size - k:
            i += 1
            pre = newhead
            newhead = newhead.next
        cur.next = head
        pre.next = None
        return newhead

问题描述:【Linked List】82. Remove Duplicates from Sorted List II
解题思路:

这道题是给一个链表,去除链表中重复的元素,只留下原链表出现过一次的数字。如 1->2->2->3 变成 1->3。

这道题和下面的 Leetcode 82 思路相同,只不过这道题不需要留下重复的元素。因此除了 Leetcode 82 中的 cur 和 last 外,还需要一个 pre 指向 cur 的前一个位置,便于把所有相同的 cur 全部删除。 同时,要使用一个标记变量 flag 来记录连续一段有没有重复的元素(flag = True),如果没有重复,只是修改 pre 和 cur 向后各移动一位;否则还要进行指针的交换。注意:比如 [1,2,2,2,2] 这种,循环结束了,但是最后 flag 为 True,因此还需要再进行一次判断,如果 flag 为 True,要进行一次指针的交换操作。

时间复杂度为 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 deleteDuplicates(self, head: ListNode) -> ListNode:
        node = ListNode(-1)
        node.next = head
        head = node
        if not head.next:
            return head.next
        # cur: 指向第一个重复的元素,last: 工作指针,pre: 是 cur 的前一个位置
        pre, cur, last = head, head.next, head.next.next
        flag = False
        while last:
            if cur.val == last.val:
                flag = True
                cur.next = last.next
            elif flag:  # 有重复
                pre.next = last
                cur = last
                flag = False    # 不要忘了修改 flag 为 False,标记下一段是否可能有重复
            elif not flag:  # 没有重复
                pre = cur
                cur = last
            last = last.next
        if flag:  # [1,1]或者[1,2,2]
             pre.next = last 
        return head.next

问题描述:【Linked List】83. Remove Duplicates from Sorted List
解题思路:

这道题是给一个链表,去除链表中重复的元素。如 1->2->2->3 变成 1->2->3。

只需要两个指针 cur 和 last,cur 指向相同元素的第一个结点,last 为工作指针,每次向后移动。剩下的就是指针的交换和移动。时间复杂度为 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 deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur, last = head, head.next
        while last:
            if cur.val == last.val:
                cur.next = last.next
            else:
                cur = cur.next
            last = last.next
        return head

问题描述:【Two Pointers】142. Linked List Cycle II
解题思路:

这道题是给一个链表,判断是否有环。如果有环,找到环的起始位置。

这道题和 Leetcode 【Two Pointers】141. Linked List Cycle 思路一致,都是先使用快慢指针(一个走一步,一个走两步)判断是否有环。

对于这道题,如果有环,还要寻找环的起始位置。思路是:定义一个指针 begin 指向链表头,然后和快慢指针的相遇点 slow(或者 fast),每一次都各走一步,直到二者相遇。证明就不写了,可以参考:LeetCode-142. Linked List Cycle II(详细证明)与龟兔赛跑算法 的证明过程。

时间复杂度为 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 detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        flag = True  # 标记是否有环
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # 有环
                flag = False
                break
        if flag:  # 无环
            return None
        begin = head
        while begin != slow:
            begin = begin.next
            slow = slow.next
        return begin # return slow

问题描述:【Linked List】143. Reorder List
解题思路:

这道题是给一个链表,按照 L0→Ln→L1→Ln-1→L2→Ln-2→… 重新排序。

首先第一种想法:遍历一次链表,将各个结点保存到 list 中,按题目顺序重新构造链表即可。更进一步,我们只需要保存后一半链表元素到 list 中,然后将 list 中的元素插入到前半段链表中。但是,这样的操作时间复杂度和空间复杂度均为 O(n)。

有没有时间复杂度为 O(n)、空间复杂度为 O(1) 的做法?因为后半段需要反过来插入,因此我们可以对后半段链表进行反转,然后再按顺序插入到前半段链表就行。链表反转可以参考 Leetcode 【Linked List】206. Reverse Linked List

实际上,当我们遇到需要从尾部操作的链表问题(如这道题和 Leetcode 【Linked List】445. Add Two Numbers II),都可以先将链表反转,然后再操作,这样就不用使用额外空间了。

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

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return head
        l1 = slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        l2 = self.reverse(slow.next)  # 后半段反转
        slow.next = None  # 断开前半段
        cur1, cur2 = l1, l2  
        while cur1 and cur2:  # 将后半段依次插入前半段
            l2 = l2.next  # 插入
            cur2.next = cur1.next
            cur1.next = cur2
            cur1 = cur2.next  # 移动
            cur2 = l2
        return l1
        
    def reverse(self, head):
        if not head or not head.next:
            return head
        pre, cur = head, head.next
        while cur:
            pre.next = cur.next  # 交换
            cur.next = head
            head = cur
            if pre != None:
                cur = pre.next  # 移动
        return head

问题描述:【Hash Table】1171. Remove Zero Sum Consecutive Nodes from Linked List
解题思路:

这道题是给一个链表,反复删去链表中总和为 0 的连续结点组成的序列,直到不存在这样的序列为止。

很明显这是一道前缀和问题。之前做过前缀和的一个专题:Leetcode【523、525、560、974】,因此需要用到 Hash Table 存储未出现的前缀和与对应位置的链表结点地址。如果再出现相同前缀和,则就删除两前缀和地址之间的元素即可(修改指针指向)。

注意: 1、要把 {0: None} 加入到 Hash Table 中,作为前缀和的出口(如 [1,2,-3] 这种情况)。 2、对于链表 [1,3,2,-3,-2,5,5,-5,1],从左到右遍历,刚开始得到的前缀和分别为 {0: add(None), 1: add(1), 4: add(3), 6: add(2), 3: add(-3)},当计算到 -2 位置时,前缀和为 3 + (-1) = 1,前缀和 1 之前在 Hash Table 中出现过,因此需要将 add(1) 的下一个地址指向 -2 的下一个地址 add(5)。但是要注意,这时候还要标记 add(1) 后面的前缀和不可用(因为已经被删除了)。因此,这个时候可以再使用一个集合 discard,用来记录删除的那些地址(从 add(1) 的下一个位置开始循环,一直到 add(-2))。因此,不仅前缀和要在之前出现过,而且前缀和地址不是 discard 中删除的地址,才可以进行删除。如果不这样做,当碰到 add(5) 时,前缀和为 6,又要删除,从而造成错误的结果。

时间复杂度为 O(n^2),空间复杂度为 O(n)。

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

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        node = ListNode(-1)
        node.next = head
        head = node
        dic = {0: head}  # 前缀和:地址
        discard = set()  # 删除的地址
        presum = 0
        cur = head.next
        while cur:
            presum += cur.val
            if presum in dic and dic[presum] not in discard:
                p = dic[presum].next  # 删除的地址保存在集合中
                while p != cur:
                    discard.add(p)
                    p = p.next
                dic[presum].next = cur.next  # 指针移动
            else:
                dic[presum] = cur
            cur = cur.next
        return head.next

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 工具推荐:BadAssMacros免杀宏生成器

    在众多的攻击方式中,钓鱼文档攻击仍然扮演者重要的地位,而随着各类安全防护设备的成熟,宏免杀一直是我们所讨论的问题,之前有MacroPack(收费版仍然好...

    鸿鹄实验室
  • Spark学习使用笔记 - Scala篇(1)

    干货满满张哈希
  • php-redis安装脚本

    dogfei
  • AVFrame转换到Mat,yuv420p转换到RGB源代码

    FFmpeg中AVFrame到OpenCV中Mat的两种转换方法 方法一:查表法 void AVFrame2Img(AVFrame *pFrame, cv::M...

    一棹烟波
  • LeetCode 分类刷题 —— Linked List

    最近有朋友问我怎么没有更新文章了,因为最近有空的时候都在刷 LeetCode,零零星星刷了快 2 个月了,也累积了不少题目了,所以最近打算把做的几百道题归类,总...

    一缕殇流化隐半边冰霜
  • 商城项目回顾整理(一)前台页面布局

    登录页面: 1 <%@ page language="java" contentType="text/html; charset=utf-8" 2 ...

    二十三年蝉
  • MySQL5.5.5安装脚本

    dogfei
  • nginx安装脚本

    dogfei
  • php安装脚本

    dogfei
  • 字典序???你是啥

    按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2。

    不太灵光的程序员
  • 第一个WPF程序(串口调试)

    本例子仅支持“ASCII”编码的串口数据发送与接收,如果需要其他编码,请自行更改,谢谢!

    CNXY
  • java开发_mysql中获取数据库表描述_源码下载

    我们需要获取表:test_table表的描述信息,然后把描述信息插入到表:data_element_config中记录结果

    Hongten
  • 图书展示案例html版

    黑泽君
  • python3验证码机器学习 python3验证码机器学习

    pip3 install pillow or easy_install Pillow

    机器学习和大数据挖掘
  • (八十四)c#Winform自定义控件-导航菜单(类Office菜单)

    https://www.cnblogs.com/bfyx/p/11364884.html

    冰封一夏
  • asp企业网站源码部分

    用户1112962
  • 带新手玩转MVC——不讲道理就是干(上)

    前言:这几天更新了几篇博客,都是关于Servlet、JSP的理解,后来又写了两种Web开发模式,发现阅读量还可以,说明JSP还是受关注的,之前有朋友评论说JSP...

    泰斗贤若如
  • My Notepad

    I have spent near more two weeks to write this Notepad application. At this mome...

    Hongten
  • 省市县三级联动

    上次找到地区编码后,就测试省市县。网上找到例子感觉不是很合适,然后修改了下。 本来是从自己数据库查询,但做测试的话,在网上找到了一个地区编码的api,然后就是跨...

    Ryan-Miao

扫码关注云+社区

领取腾讯云代金券