【2025-02-28】基础算法：前后指针

用户11029137

发布于 2025-03-01 22:01:22

7700

代码可运行

运行总次数：0

代码可运行

📝前言说明： ●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频 ●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。 ●文章中的理解仅为个人理解。 ●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

一，视频题目

237. 删除链表中的节点

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 因为不知道要删除节点的前一个节点，所以先copy后一个值到node节点，然后再把后一个节点删掉
        node.val = node.next.val
        node.next = node.next.next

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

当需要删除第一个节点的时候，需要dummy node 快慢指针：先让快指针走n步，再让慢指针开始走，是两个指针始终保持n的距离（即左指针要再走n步才能走到右指针的位置）当快指针走到倒数第1个节点时，慢指针指向倒数第n-1个节点

# 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]:
        left = right = dummy = ListNode(next = head)
        for _ in range(n):
            right = right.next
        while right.next: # 让left停在要删除节点的前一个位置
            left = left.next
            right = right.next
        left.next = left.next.next
        return dummy.next

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

# 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: Optional[ListNode]) -> Optional[ListNode]:
        # 让快指针指向值不同的节点
        if head is None:
            return head
        cur = head
        while cur.next:
            if cur.next.val == cur.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

82. 删除排序链表中的重复元素 II

# 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: Optional[ListNode]) -> Optional[ListNode]:
        # 当有重复节点的时候，这些节点都要被删除，可能删除头结点所以需要哨兵
        cur = dummy = ListNode(next = head)
        while cur.next and cur.next.next: # 剩余节点数>2时要判断
            val = cur.next.val # 记录需要删除的元素的值
            if val == cur.next.next.val: 
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next # 循环跳过所有重复的元素
            else:
                cur = cur.next
        return dummy.next

二，课后作业

203. 移除链表元素

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        cur = dummy = ListNode(next = head)
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

3217. 从链表中移除在数组中存在的节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        cur = hummy = ListNode(next = head)
        st = set(nums)
        while cur.next:
            if cur.next.val in st:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return hummy.next

统计次数用hasmap 只判断是否存在：使用set消除重复项

2487. 从链表中移除节点

# 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: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 每次移动完以后要回溯？
        # 回溯不好操作，所以我们需要向一个能在遇到元素时就能判断是否能删除的办法
        # 反转链表，当遇到比当前记录元素小的节点就删除
        head = self.reverseList(head)
        cur = head
        while cur.next:
            if cur.next.val < cur.val:
                cur.next = cur.next.next
            elif cur.next.val >= cur.val:
                cur = cur.next
        return self.reverseList(head)

1669. 合并两个链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        start1 = list1
        for _ in range(a-1):
            start1 = start1.next
        end1 = start1
        for _ in range(b-a+2):
            end1 = end1.next
        end2 = list2
        while end2.next:
            end2 = end2.next
        
        start1.next = list2
        end2.next = end1
        return list1

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

指针