LeetCode 0203.移除链表元素【Go】

移除链表元素

LeetCode203. 移除链表元素

题目描述

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

示例 1：

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

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

思路

题目要求

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

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

注意

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

代码

Go

/**
 * 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
}

Link

GitHub