2025-03-01：交换后字典序最小的字符串。用go语言，给定一个整数数组 nums 和一个链表的头节点 head，需要从链表

福大大架构师每日一题

发布于 2025-03-03 15:30:51

4300

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-01：交换后字典序最小的字符串。用go语言，给定一个整数数组 nums 和一个链表的头节点 head，需要从链表中删除所有在 nums 数组中出现的节点。最后，返回修改后链表的头节点。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

nums 中的所有元素都是唯一的。

链表中的节点数在 [1, 100000] 的范围内。

1 <= Node.val <= 100000。

输入保证链表中至少有一个值没有在 nums 中出现过。

输入： nums = [1,2,3], head = [1,2,3,4,5]。

输出： [4,5]。

答案2025-03-01：

chatgpt[1]

题目来自leetcode3217。

大体步骤如下：

1.创建一个空的字典 has 用于存储 nums 中的元素，这里使用了 map[int]bool 类型。

2.遍历 nums 数组，将数组中的每个元素作为 key 存入字典 has 中，并赋值为 true。

3.创建一个虚拟节点 dummy，其下一个节点指向给定的链表头节点 head。

4.创建一个指针 cur 指向 dummy，用于遍历链表。

5.当 cur 的下一个节点不为空时，进行以下判断：

• 如果 has 中包含 cur.Next.Val：表示当前节点需要删除，直接将 cur.Next 指向下下个节点，实现删除操作。
• 否则，将 cur 指向下一个节点，继续向后移动。

6.返回修改后链表的头节点，即 dummy.Next。

总的时间复杂度：遍历链表的时间复杂度为 O(n)，其中 n 为链表节点数。构建字典的时间复杂度为 O(m)，其中 m 为 nums 数组的长度。所以总体时间复杂度为 O(n + m)。

总的额外空间复杂度：除了存储链表和数组外，额外使用了一个字典 has 来存储 nums 中的元素，因此额外空间复杂度为 O(m)，其中 m 为 nums 数组的长度。

Go完整代码如下：

package main

import (
    "fmt"
)

type ListNode struct {
    Val  int
    Next *ListNode
}

func modifiedList(nums []int, head *ListNode) *ListNode {
    has := make(map[int]bool, len(nums)) // 预分配空间
    for _, x := range nums {
        has[x] = true
    }
    dummy := &ListNode{Next: head}
    cur := dummy
    for cur.Next != nil {
        if has[cur.Next.Val] {
            cur.Next = cur.Next.Next // 删除
        } else {
            cur = cur.Next // 向后移动
        }
    }
    return dummy.Next
}

func main() {
    nums := []int{1, 2, 3}
    head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
    result := modifiedList(nums, head)
    for result != nil {
        fmt.Print(result.Val, " ")
        result = result.Next
    }
}

Python完整代码如下：

# -*-coding:utf-8-*-

classListNode:
    def__init__(self, val=0, next=None):
        self.val = val
        self.next = next

defmodified_list(nums, head):
    has = set(nums)  # 使用集合来存储nums中的值
    dummy = ListNode(next=head)  # 创建一个虚拟头节点
    cur = dummy
    
    while cur.nextisnotNone:
        if cur.next.val in has:
            cur.next = cur.next.next# 删除节点
        else:
            cur = cur.next# 向后移动
    
    return dummy.next# 返回新的头节点

defmain():
    nums = [1, 2, 3]
    head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    result = modified_list(nums, head)
    
    while result isnotNone:
        print(result.val, end=" ")
        result = result.next

if __name__ == "__main__":
    main()