力扣——算法入门计划第五天

简介: 力扣(LeetCode)是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷,力扣为全球程序员提供了专业的IT技术职业化提升平台,有效帮助程序员实现快速进步和长期成长。 此外,力扣(LeetCode)致力于解决程序员技术评估、培训、职业匹配的痛点,逐步引领互联网技术求职和招聘迈向专业化。

 目录

🍕题目

🍔方法一:

🍟代码

🍔方法二:快慢指针法

🍟代码:

🍟解读while为什么判断fast.next 和fast?而不是fast.next.next 和fast.next ?

🍕题目

🍔方法一:暴力解法

🍟代码

🍔方法二:双指针

🍟 代码


🍕题目

876. 链表的中间结点

image.png

🍔方法一:

这里借用一下题解里的图

image.png

通过数组访问,我们可以发现个结论:中间节点在数组的索引为N/2      

🍟代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]

image.gif

image.png

🍔方法二:快慢指针法

两个指针 slowfast 一起遍历链表。slow 一次走一步,fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。

这里我借用题解的图

image.gifimage.png

拿例题来说

image.png

🍟代码:

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

image.gif

🍟解读while为什么判断fast.next 和fast?而不是fast.next.next 和fast.next ?

liweiwei1419大佬的图

因为题目如果有两个中间结点,则返回第二个中间结点!!!

判断fast.next 和fast

image.png

fast.next.next 和fast.next

image.png

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

image.gif

image.png

🍕题目

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

image.png

🍔方法一:暴力解法

1)找到链表长度

2)删除从表头开始的(L-n+1)节点

技巧:

在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的 next 指针指向链表的头节点。这样一来,我们就不需要对头节点进行特殊的判断了

为了与题目中的 n保持一致,节点的编号从 1 开始,头节点为编号 1的节点。

为了方便删除操作,我们可以从哑节点开始遍历 L-n+1个节点。当遍历到第 L-n+1 个节点时,它的下一个节点就是我们需要删除的节点,这样我们只需要修改一次指针,就能完成删除操作。

image.png

🍟代码

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head: ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        dummy = ListNode(0, head)
        length = getLength(head)
        cur = dummy
        for i in range(1, length - n + 1):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

image.gif

image.png

🍔方法二:双指针

由于我们需要找到倒数第 n个节点,因此我们可以使用两个指针first 和 second同时对链表进行遍历,并且firstt 比 second超前 n个节点。当 first遍历到链表的末尾时,second 就恰好处于倒数第 n个节点。

在这之后,我们同时使用first 和second 对链表进行遍历。当first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 n 个节点

image.png

🍟 代码

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next


image.png


相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
39 0
|
18天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
27 2
|
2月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
2月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
2月前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
2月前
|
机器学习/深度学习 算法 API
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
机器学习入门(五):KNN概述 | K 近邻算法 API,K值选择问题
|
2月前
|
算法
【链表】算法题(一) ----- 力扣 / 牛客
【链表】算法题(一) ----- 力扣 / 牛客
|
2月前
|
算法
【顺序表】算法题 --- 力扣
【顺序表】算法题 --- 力扣
|
2月前
|
机器学习/深度学习 算法
机器学习入门:梯度下降算法(上)
机器学习入门:梯度下降算法(上)
下一篇
无影云桌面