LeetCode 203. 移除链表元素

题目描述

🔥 203. 移除链表元素

image-20230305201613193

思路分析

  1. 使用一个虚拟头节点来处理头节点可能被删除的情况。
  2. 使用一个指针 cur 来遍历链表。
  3. 如果 cur.Next 的值等于 val，则跳过 cur.Next 节点。
  4. 如果 cur.Next 的值不等于 val，则移动 cur 到下一个节点。
  5. 继续遍历直到链表结束。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func removeElements(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy

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

	return dummy.Next
}
  • 时间复杂度: O (n)，其中 n 是链表的长度。我们只需要遍历链表一次。
  • 空间复杂度: O (1)，我们只使用了常数级别的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13

func removeElements(head *ListNode, val int) *ListNode {
	dummy := &ListNode{Next: head}
	pre, cur := dummy, head
	for cur != nil {
		if cur.Val == val {
			pre.Next = cur.Next
		} else {
			pre = cur
		}
		cur = cur.Next
	}
	return dummy.Next
}

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2023/17566770
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！