leetcode算法

leetcode链表之删除链表结点

2022-03-24  本文已影响0人  小奚有话说

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

文章出现的代码都是python3

题目

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

示例1:

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

示例2:

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

思路

由于链表是已经排序好的,只需要判断当前结点的值是否和下一个结点的值是否相等,如果相等,删除下一个结点即可

代码:

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: return head
        cur = head
        while cur.next:
            # 如果当前结点的值等于下一结点的值,直接将当前指针指向下下个结点
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            # 否则的话直接遍历即可
            else:
                cur = cur.next
        return head

82、删除排序链表中的重复元素2

题目

给定一个已排序的链表的头 head删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表

示例1:

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

示例2:

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

思路:

删除重复数字的节点,也就是需要重复数字的上一个结点,然后通过重复值进行迭代删除即可。

代码:

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head: return head
        # 由于删除结点的时候,可能会删除头结点,创建一个虚拟结点
        cur = vHead = ListNode(0, head)
        # 需要判断下个结点的值和下下个结点的值是否重复
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                # 临时变量存储,避免结点删除之后,值丢失的问题
                temp = cur.next.val
                # 遍历删除重复结点
                while cur.next and cur.next.val == temp:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return vHead.next

203、删除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

示例1:

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

示例2:

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

示例3

输入:head = [7,7,7,7], val = 7
输出:[]

思路:

遍历比较元素大小,并删除

代码:

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head: return head
        vHead = ListNode(0, head)
        cur = vHead
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return vHead.next

237、删除链表中的结点

题目

请编写一个函数,用于 删除单链表中某个特定节点 。在设计函数时需要注意,你无法访问链表的头节点 head ,只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例1:

输入:head = [4,5,1,9], node = 5
输出:[4,1,9]

示例2:

输入:head = [4,5,1,9], node = 1
输出:[4,5,9]

示例3:

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

示例4:

输入:head = [0,1], node = 0
输出:[1]

示例5:

输入:head = [-3,5,-99], node = -3
输出:[5,-99]

思路:

按照一般思路,删除链表中的结点,一般会想到找结点的上一个结点进行删除,这道题没有给头结点以及上一个结点,所以这种方法行不通,并且删除的结点不是尾结点,也就是说我们可以将这个结点改成下一个结点,然后删除下一个结点就行。

代码:

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

移除重复结点

题目:

编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

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

示例2:

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

思路:

这道题和上面的不同点是链表未排序,可以使用hash表存储数据,然后判断已经出现则删除

代码:

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        cur = ListNode(0, head)
        seen = set()
        # 判断下一个结点的值,这样有利于删除结点
        while cur.next:
            val = cur.next.val
            if val in seen:
                cur.next = cur.next.next
            else:
                seen.add(val)
                cur = cur.next
        return head

2095、删除链表的中间结点

题目:

给你一个链表的头节点 head 。删除 链表的 中间节点 ,并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点(下标从 0 开始),其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

示例1:

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

示例2:

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

示例3:

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

思路

使用快慢指针找到中间结点的前置结点,删除掉中间结点

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        # 慢节点指向虚拟头结点,这样在遍历的时候,慢节点就会指向中间结点的前置结点
        slow = vhead = ListNode(0, head)
        fast = head
        # 使用快慢结点遍历,找到中间结点
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 此时慢节点指向的是中间结点的前置结点,删除中间结点即可
        slow.next = slow.next.next
        return vhead.next
上一篇下一篇

猜你喜欢

热点阅读