golang leetcode203移除链表元素

2023-12-28 20:16:37

移除链表元素 leetcode203

初版方法 迭代 虚拟头节点

使用迭代解决 ,虚拟头节点
没有使用给出的链表,选择重建了一个链表,时间、空间复杂度都增加

func removeElements(head *ListNode, val int) *ListNode {
	//遍历节点

	//targetList := new(ListNode) //golang自建类型可以使用make,如slice等;这里我们自定义类型使用new,new返回指针
	targetList := &ListNode{} //直接实例化,可能更快

	middle := targetList //target作为头节点

	for head != nil {
		if head.Val == val { //检测链表中的val是否等于val

		} else { //如果不用删除,直接赋值
			middle.Next = &ListNode{Val: head.Val}
			middle = middle.Next
		}
		head = head.Next
	}

	return targetList.Next
}

改进 迭代 虚拟头节点

// 新版本 迭代 虚拟头节点
func removeElements(head *ListNode, val int) *ListNode {
	dummyHead := new(ListNode) //dummyHead为虚拟头节点
	dummyHead.Next = head      //定义虚拟头节点的下一个节点为原链表第一个节点
	cur := dummyHead

	//虚拟头节点的使用可以不用考虑原链表的头节点的val为Val,不能直接删除的问题
	//我们检查的不是当前节点的val是否为Val,而是当前的next.val,是为了方便删除符合条件的节点;如果选择检查当前节点的val,则不好删除当前节点,大家可以编程体会

	//先定义逻辑
	//首先是循环的定义,只要head.next!=nil,就继续循环

	//如果原链表 循环到的节点的next.val为 给定的Val ,则将head.next->head.next.next,即下一个指针跳过当前节点,且此时这里是不保存下一个节点的,防止下一个节点的val也是Val
	//如果为空 ,则return dummyHead.next

	for cur.Next != nil {

		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}

	}

	return dummyHead.Next

}

使用迭代 直接使用原链表 不使用头节点

func removeElements(head *ListNode, val int) *ListNode {

	//依旧是先定义逻辑

	//如果是 原链表的头节点为val的话,直接将head=head。next,且当前过程持续,防止头节点后面的节点也为Val
	//这里前置循环 并且要判定head 是否为nil,防止出错

	//这之后再定义cur:=head
	//这里再判定cur.next.val如果等于val,cur.next=cur.next.next(具体原因看上面使用虚拟头节点部分),跳过下一个节点

	//注意:因为要判定不使用虚拟头节点,在循环中要判断循环到的节点是否为nil,防止出错

	for head != nil && head.Val == val {
		head = head.Next
	}
	cur := head

	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}

	return head

}

递归方法

首先是建立链表的思路
我选择寻求gpt的帮助 :)

构建递归的思路通常遵循以下几个步骤:

  • 确定递归结束条件:这是最重要的一步,递归必须有一个明确的结束条件,否则会导致无限递归和栈溢出。结束条件通常是当问题规模缩减到最小或达到某个特定状态时。

  • 找到问题的递归式:确定如何将问题分解成更小的子问题。递归的核心思想是将大问题分解成结构或逻辑上类似的小问题。

  • 调用自身解决子问题:在函数中调用自身(递归调用)来解决这些子问题。这些子问题的解决方式应与原问题相同。

  • 整合子问题的解决结果:递归调用后,通常需要整合或处理这些子问题的结果来得到最终答案。

  • 优化(可选):对于某些递归问题,可能会出现重复计算的情况,可以通过技巧如记忆化(memoization)来优化性能。

那么我们将结合leetcode203进行上述思路进行解题

要使用递归方法解决删除链表中所有满足 Node.val == val 的节点问题,可以遵循以下递归思路:

  • 递归结束条件:当当前节点为 null 时,表示已经到达链表末尾,递归结束。在这种情况下,直接返回 null。

  • 递归式
    检查当前节点(假设为 head)的值是否等于 val。
    如果是,我们需要删除这个节点,这意味着需要将其父节点(递归中的上一个节点)连接到它的下一个节点。
    但在递归中,我们没有直接的方式来访问父节点,因此我们通过返回下一个节点(head.next)来实现这一点。

  • 调用自身:对于每个节点,调用递归函数处理它的下一个节点(即,调用自身传递 head.next 和 val)。

  • 整合子问题的解决结果:如果当前节点的值不等于 val,那么我们需要保留这个节点,并将其 next 指针指向递归调用的结果。否则,直接返回递归调用的结果,即 head.next 的递归处理结果。

  • 返回新的头节点:递归的最终结果是新的链表头节点,它可能与原始链表的头节点不同,尤其是当原始头节点的值等于 val 时。

// 递归
func removeElements(head *ListNode, val int) *ListNode {

	//放在递归开头的为 结束条件 ,其应该return一个结果,结束本次递归
	//即本次递归传入的 head为空,不再进行后续递归,将尾节点设置为空
	if head != nil {
		return head
	}

	//调用自身
	//修改子节点
	head.Next = removeElements(head.Next, val) //我们也可以通过这个式子理解 下面的返回 返回到.next

	//递归式-整合子问题的解决成果
	//返回到父节点
	if head.Val == val {
		return head.Next //如果当前节点的val等于val则舍弃该节点
	}
	return head
}

文章来源:https://blog.csdn.net/kingsill/article/details/135276042
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。