【基础算法精讲-学习记录】前后指针

视频学习记录

https://www.bilibili.com/video/BV1VP4y1Q71e

• 前后指针，标题看着和【基础算法精讲-学习记录】快慢指针差不多，都是一前一后两个指针，但是要解决的重点不同。

• 快慢指针强调的是两个指针行动的速度不同，这样才方便找到中间节点；这次的前后指针则是强调偏快的指针是作为侦查兵去检查重复值等，这样才方便链表去重。

例题和课后作业代码记录

237. 删除链表中的节点

https://leetcode.cn/problems/delete-node-in-a-linked-list/description/

# 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.
        """
        # 这题很脑筋急转弯哈，直接给的要删除的点
        # 常规删除，需要删除前后的结点，但由于本题确认不是最后一个结点
        # 所以只要把下个结点的值覆盖要删除的点，然后删除下个结点即可
        # 时间空间都是O1
        nxt = node.next 
        node.val = nxt.val 
        node.next = nxt.next
        

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

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

# 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]:
        # 时间：还是得遍历链表On
        # 空间：无额外变量O1
        dummy = ListNode(next = head)
        l, r = dummy, dummy
        for _ in range(n):
            r = r.next # 题目确认倒数的那个值不大于链表长度，视为l和r的间隔

        while r.next: # 把 r 锚定为最后一个节点
            l, r = l.next, r.next 
        
        l.next = l.next.next 
        return dummy.next

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/

# 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]:
        # 时间：遍历一次链表On
        # 空间：没有额外变量O1
        l = head
        r = head

        while r:
            if l.val != r.val:
                l = l.next
                l.val = r.val 
            r = r.next
        
        if l:
            l.next = None
                
        return head

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

# 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]:
        # 时间：遍历一次链表On
        # 空间：无额外变量O1
        if head is None or head.next is None: # 对于链表长度0或1就直接传，不可能重复
            return head

        dummy = ListNode(next=head)
        cur = dummy
        while cur and cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                nxt = cur.next.next # 用nxt找到下个不同的值，或者空
                while nxt and nxt.val == cur.next.val:# 第一个纺织品遍历到末尾
                    nxt = nxt.next
                cur.next = nxt
            else: 
                cur = cur.next # 必须确定接下来的两个值不同，那么第一个值是必定保留的
            # print(cur.val)
        
        return dummy.next
        

203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

# 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]:
        # 时间：遍历一次链表，On
        # 空间：没有额外存储变量，O1
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next 
            else:
                cur = cur.next 
        return dummy.next

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

https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array/description/

# 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]:
        # 时间：遍历一次链表，On
        # 空间：额外存储变量nums，Om
        rec = set(nums)
        dummy = ListNode(next=head)
        cur = dummy
        while cur.next:
            if cur.next.val in rec:
                cur.next = cur.next.next 
            else:
                cur = cur.next 
        return dummy.next

2487. 从链表中移除节点

https://leetcode.cn/problems/remove-nodes-from-linked-list/description/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 如果用反转链表，就不需要记录值，一旦下个值比当前小就删除，还不用遍历第二遍，那就只有On的时间
        # 时间：两次遍历链表，第一次收集值，第二次删除，On
        # 空间：记录链表值一遍，On
        nums = []
        cur = head 
        while cur:
            nums.append(cur.val)
            cur = cur.next 
        
        if len(nums) == 1: # 排除链表长度为1的情况
            return head

        for i in range(len(nums)-2, -1, -1): # 最大后缀
            nums[i] = nums[i] if nums[i] > nums[i+1] else nums[i+1]

        dummy = ListNode(next=head)
        cur = dummy
        for i in range(len(nums)):
            if cur.next.val < nums[i]:
                cur.next = cur.next.next 
            else:
                cur = cur.next 
        
        return dummy.next 

1669. 合并两个链表

https://leetcode.cn/problems/merge-in-between-linked-lists/description/

# 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:
        # 由于a和b下标不会波及list1的开头，所以可以不用哨兵节点
        # 时间：遍历list1和list2各一遍，Om+n
        # 空间：没有额外存储变量，O1
        cur = list1
        for _ in range(a-1):
            cur = cur.next 
        start = cur # 被删除部分的前一个点
        for _ in range(b-a+1):
            cur = cur.next 
        nxt = cur.next # 被删除部分的下个点

        start.next = list2 
        cur = list2 
        while cur.next:
            cur = cur.next 
        
        cur.next = nxt 
        return list1