golang leetcode203移除链表元素

移除链表元素 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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

改进 迭代 虚拟头节点

// 新版本 迭代 虚拟头节点
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

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

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

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

递归方法

首先是建立链表的思路
我选择寻求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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21