IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Task07:双指针 -> 正文阅读

[数据结构与算法]Task07:双指针

1. 视频题目

1.1 反转链表

1.1.1 描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:
在这里插入图片描述

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:
在这里插入图片描述

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

1.1.2 代码

新建另外一个带头结点的链表,然后使用头插法,新元素从头部插入

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        while head:
            temp = head.next
            head.next = dummy.next
            dummy.next = head
            head = temp
        return dummy.next

1.1.3 总结

因为是反转链表,所以要用头插法

1.2 删除链表的倒数第 N 个结点

1.2.1 描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:
在这里插入图片描述

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶:你能尝试使用一趟扫描实现吗?

1.2.2 代码

链表题目,先新建一个空的头结点,然后从这里开始。经验之谈,一般都挺好使

要删除倒数第n个结点,就是搞出两个间隔为n的双指针。注意,是间隔为n

一个到达最后结点,也就是.next==null,另一个就是被删除结点的前一个结点

所以使得slow指针指向slow.next.next,即跳过被删除的slow.next即可

然后发现这个方法对于边界条件如示例23都适用,直接给过

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        fast = dummy
        while n>0 and fast:
            fast = fast.next
            n -= 1
        slow = dummy
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

1.2.3 总结

本题再一次证明了,遇到链表题目先建一个新的头结点再说

然后就是,要删除链表的一个结点,一般是操作其前一个结点

还有就是,一定要注意间隔,这和长度不是一个概念,两者相差1

2. 作业题目

2.1 删除排序链表中的重复元素

2.1.1 描述

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

示例 1:
在这里插入图片描述

输入:head = [1,1,2]
输出:[1,2]

示例 2:
在这里插入图片描述

输入:head = [1,1,2,3,3]
输出:[1,2,3]

提示:

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

2.1.2 代码

直接判断当前结点的下一个结点的值是否与当前结点的值相同

如果相同则跳过结点,即当前指针.指向.next.next

需要注意的是条件的判断,当前指针不为空主要是防止链表为空

下一个结点不为空则是因为需要取下一个结点的值进行判断

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        while head and head.next:
            if head.val == head.next.val :
                head.next = head.next.next
            else:
                head = head.next
        return dummy.next        

2.1.3 总结

本题再一次证明了,遇到链表题目先建一个新的头结点再说

然后就是,要删除链表的一个结点,一般是操作其前一个结点

2.2 环形链表

2.2.1 描述

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:
在这里插入图片描述

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:
在这里插入图片描述

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

在这里插入图片描述

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

2.2.2 代码

判断成环,经典的快慢指针问题,快指针每次走两步,慢指针一步

如果两者相遇则证明一定有环,但凡出现None就证明无环且到尽头

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head and head.next:
            fast = head.next.next
        else:
            fast = None
        slow = head
        while fast and slow and fast.next:
            if fast != slow:
                slow = slow.next
                fast = fast.next.next
            else:
                return True
        
        return False

2.2.3 总结

涉及到next的问题一定要确保结点不为空,否则引用值无效

也就是说,我们需要确保引用.next.val的那个结点不为空

尤其是当这个引用本身就包含其他引用,也就是.next.next的情况

2.3 排序链表

2.3.1 描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

示例 1:
在这里插入图片描述

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:
在这里插入图片描述

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

2.3.2 代码

刚开始看到 O(n log n) 我就想到了快排,然后感觉太复杂了,改用插入排序

然后就…超时了,题目上不是说O(n log n)是进阶吗?然后看题解发现这是题目要求…

按照这个时间复杂度限制的要求,考虑到链表不同于数组,题解给的是归并排序

那就是有划分与合并的两个步骤,划分就是单纯的划分就好,合并是合并两个有序链表

所以递归的跳出条件,就是最终划分出两个单个元素,然后在合并当中按大小排序

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            # 如果为空就返回,可能是空链表
            if head.next == tail:
                head.next = None
                return head
            # 只有两个元素的情况下,返回前者
            # 因为上一次的mid同时被传入左右两个部分
            # 所以这里默认右边的mid是有效的而左边无效
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
                # fast始终更快一步
            mid = slow
            # fast到头,slow就是mid
            return merge(sortFunc(head, mid), sortFunc(mid, tail))
            
        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummyHead = ListNode(0)
            # 新链表的头结点
            temp, temp1, temp2 = dummyHead, head1, head2
            # 临时指针用于移动
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                # 挑选出较小的加入新链表
                temp = temp.next
                # 更新新链表临时指针
            if temp1:
                temp.next = temp1
            elif temp2:
                temp.next = temp2
            # 如果还有没走完的,直接加入新链表
            return dummyHead.next
        
        return sortFunc(head, None)

2.3.3 总结

归并排序有划分与合并的两个步骤,划分就是单纯的划分就好,合并是合并两个有序链表

所以递归的跳出条件,就是最终划分出两个单个元素,然后在合并当中按大小排序

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-02-28 15:50:37  更:2022-02-28 15:52:34 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 16:50:19-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码