返回

LeetCode 0203.移除链表元素

移除链表元素

LeetCode203. 移除链表元素

题目描述

给你一个链表的头节点head和一个整数 val,请你删除链表中所有满足 Node.val == val 的节点,并返回新的头节点

示例 1:

1
2
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

1
2
输入:head = [], val = 1
输出:[]

示例 3:

1
2
输入:head = [7,7,7,7], val = 7
输出:[]

思路

题目要求

  • 给定一个链表的头节点和一个目标元素,要求删除链表中与目标元素相同的节点
  • 要求返回删除目标元素后的链表的头节点

由题意可知此题为单链表,单链表只能指向下一个元素,移除操作只需要让节点的next的指针指向下下一个节点。

注意

  • 若要移除头节点,操作与其他节点不一样,因为移除节点是通过要移除的元素的前一个节点来移除节点,而头节点前没有节点,所以需要单独写一个移除操作。为了使头节点的移除操作与其他节点保持一致,我们可以在头节点前再添加一个结点,该节点数据域为空,指针域指向头节点。
  • 链表有三种:单链表(数据域+指针域)、循环链表(数据域+指针域)、双链表(指针域+数据域+指针域)
  • 为了防止头节点为空,产生编译错误,所以应在循坏判断条件中判断当前节点的下一个节点是否非空
  • 最后返回的是第一个存储元素的节点,即return dummyHead.Next

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := new(ListNode)
    dummyHead.Next = head
    for p := dummyHead; p != nil && p.Next != nil; {
        if p.Next.Val == val {
            p.Next = p.Next.Next
        } else {
            p = p.Next
        }
    }
    return dummyHead.Next
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy