GIS与Climate

V1

2022/09/24阅读:15主题:默认主题

算法60天:Day 4-链表中的强大快慢指针

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day4,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的,具体可以看参考链接【1】。

今日知识点

链表理论基础:

  • 链表是一种串联、线性结构
  • 每个节点有两部分组成,值域和指针域,指针域存放指向下一个节点的指针;
  • 最后一个节点的指针域指向null(注意不同语言的写法,比如python是None);

今日题目

  1. 两两交换链表中的节点(24)

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

链接:https://leetcode.cn/problems/swap-nodes-in-pairs/

解题思路

  • 两两交换,跟翻转链表有点像(假设只有两个节点),只不过要复杂点(需要把多个链表链接起来);
  • 因为是两两交换,所以指针的移动间隔为1,也就是每两个节点进行一次处理,而不是顺次进行处理(循环的条件要注意);
  • 返回新链表的头节点,所以虚拟节点就很重要了;
交换的顺序
交换的顺序
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vir_ln = ListNode(next=head)
        pre = vir_ln
        while pre.next and pre.next.next:
            cur = pre.next
            post = pre.next.next

            temp = post.next # 先保存下
            pre.next = post # 第一步
            post.next = cur # 第二步
            cur.next = temp # 第三步

            pre = pre.next.next # 更新指针,也就是循环条件

        return vir_ln.next
  • 记住上面的顺序,然后依次修改相应节点的指针(箭头就是代表流向、指针);
  • 最后一步更新pre的时候不能直接写pre=post;
  1. 删除链表的倒数第N个节点(19)

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

链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

解题思路

  • 删除不难,之前已经写过,但是对于链表来说没有像数组一样的下标,所以难点在于找到倒数第N个节点;
  • 双指针法:让快慢指针相隔n-1个节点,当快指针到达链表末尾的时候,慢指针对应的就是我们要删除的节点;
  • 找到了要删除的节点,但是删除这个节点需要操作的是当前节点的上一个节点,所以直接让快慢指针相隔n个节点即可直接找到我们要操作的节点;
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        vir_ln = ListNode(next=head)
        slow,fast = vir_ln,vir_ln
        while n:
            fast = fast.next
            n -= 1
        while fast.next!=None:
            slow,fast=slow.next,fast.next
        slow.next = slow.next.next
        return vir_ln.next
  • 操作的指针是待删除对象的前一个,所以初始化的时候slow和fast应该是虚拟头节点;
  1. 链表相交(面试题02.07)

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

链接:https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

解题思路

  • 个人感觉这道题重在理解,想象从全班随机抽取n和m个小朋友组成两个队伍(有放回的抽取),然后把两个队伍合并成一个队伍,那么如果这两个队伍中有人被抽到了两次,则这两个队伍一定能够形成一个环+尾巴的形式(也就是说两个队伍至少大于等于1个交点);
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return None
        
        curA, curB = headA,headB

        while curA!=curB:
            curA = curA.next if curA else headB
            curB = curB.next if curB else headA
        
        return curA
  • 链表相等指的是内存地址相等,那么相交指的就是两个节点的指针指向了同一块内存区域;
  1. 环形链表(142)

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

链接:https://leetcode.cn/problems/linked-list-cycle-ii

解题思路

  • 有没有环的判断其实比较简单,就是中学物理中学的追及问题,使用双指针,让快的比慢的每次多走一步,如果存在环,那么快的最终一定会在环中某一点相遇,就好比两个人在操场跑步,跑得快的终有一刻会领先跑得慢的同学一圈,那么就是相遇了;
  • 如果存在环,难点就在于找到环的入口,具体可以去看参考【1】的讲解,有数学公式上的推理,比较详细了;
# 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, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 如果相遇
            if slow == fast:
                p = head
                q = slow
                while p!=q:
                    p = p.next
                    q = q.next
                return p

        return None
  • 不要忘记了没有环的情况下返回None;

补充知识点

  1. 链表的几种类型

上面说的是最简单的链表,实际上链表有几种:

  • 单链表
单链表
单链表
  • 双链表:一个节点有两个指针域,分别指向前一个和后一个节点;
双链表
双链表
  • 循环链表:单链表的特殊情况,首尾相连。
循环链表
循环链表
  1. 链表的存储方式

数组在内存中是连续存储的,但是链表不是,因为链表有指针,可以顺利找到下一个元素。

  1. 链表与数组的性能分析

今日思考

  1. 为什么在有环的情况下快慢指针一定会在环中某个节点相遇?

想象两个同学在操作跑步。。

  1. 为什么存在环的时候,从头节点出发的指针一定与慢指针在环的入口相遇?

看参考【1】的数学推导。。。

参考

【1】代码随想录:https://programmercarl.com/

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注