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

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()

在这里插入图片描述引用链接