移除链表元素

学习文本来源:代码随想录

力扣地址

题意:删除链表中等于给定值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
  • 输出:[]

思路

这里以链表 1->4->2->4 来举例,移除元素4。 得出1->2

那么因为单链表的特殊性,只能指向下一个节点,刚刚删除的是链表的中第二个,和第四个节点,那么如果删除的是头结点又该怎么办呢?

这里涉及如下链表操作的两种方式:

  • 直接使用原来的链表来进行删除操作。
  • 设置一个虚拟头节点在进行删除操作。

来看第一种操作:直接使用原来的链表来进行移除。

移除头节点和移除其他节点是不一样得到,因为链表的其他节点都是通过前一个节点来移除当前节点,而头节点没有前一个节点。

所以头节点如何移除呢,其实只要将头结点移动到后一位就行了,这样就从链表中移除了一个头结点。

这样移除了一个头结点,是不是发现,在单链表中移除头结点和移除其他节点的操作方式不一样,其实在写代码的时候也会发现,需要单独写一段逻辑来处理移除头结点的情况。

那么可不可以以一种统一的逻辑来移除链表节点呢。

其实可以设置一个虚拟头结点,这样原链表的所有节点都可以按照统一的方式进行移除可。

来看看如何设置一个虚拟头。依然还是在这个链表中移除1.

这里来个链表加个虚拟头结点为新的头节点,此时要移除这个旧头结点元素1.

这样是不是可以使用移除其他节点的方式统一了呢?

来看一下,如何移除元素1呢,还是熟悉的方式。

最后呢子啊题目中return的时候别忘记return dummy->next,这才是新的头结点

直接使用原来的链表来进行移除节点操作:
golang:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    now := head
    if head == nil { return head }
    for now.Next != nil {
        if now.Next.Val == val {
            now.Next = now.Next.Next
        } else {
            now = now.Next
        }
    }
    if head.Val == val {
        head = head.Next
    }
    return head
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

设置一个虚拟头结点在进行移除操作:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    newHead := &ListNode{0,head}
    now := newHead
    for now.Next != nil {
        if now.Next.Val == val {
            now.Next = now.Next.Next
        } else {
            now = now.Next
        }
    }
    return newHead.Next
}
Last modification:May 28, 2024
如果觉得我的文章对你有用,请收藏本站