您现在的位置是:首页 >其他 >【LeetCode】203,移除链表元素。 难度等级:简单。链表入门题目,值得深入研究。网站首页其他

【LeetCode】203,移除链表元素。 难度等级:简单。链表入门题目,值得深入研究。

ctrl A_ctrl C_ctrl V 2024-06-17 11:19:03
简介【LeetCode】203,移除链表元素。 难度等级:简单。链表入门题目,值得深入研究。

【LeetCode】203,移除链表元素。 难度等级:简单。

本题是链表入门题目,值得深入研究。

一、题目

在这里插入图片描述

二、解答:迭代法,引入一个新的头结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
    	# 由于链表的头节点 head 有可能需要被删除,而删除头结点比较麻烦(因为需要判断链表是否为空)
    	# 所以创建一个extraList指向head,使得head不是头结点且新的链表不是空链表;删除非空链表的结点是很容易的
        extraList=ListNode(-1,head)
        temp=extraList
        while temp.next!=None:
            if temp.next.val==val:
                temp.next=temp.next.next
            else:
                temp=temp.next
        return extraList.next

三、难点解释

这里有个难点,就是temp和extraList的关系。

(1)temp 只有在被初始化时和extraList相同,进入 while 循环后二者就不相同了,且没有任何关系。

(2)extraList 一直指向 以head为头结点的链表,extraList指向不变,但 以head为头结点的链表 被temp改变了;这就是 extraList 链表会什么会改变的原因。

(3)temp 如何改变 extraList :

以 head = [1,2,6,3,4,5,6], val = 6 为例

1,初始化:extraList = [-1,2,6,3,4,5,6] , temp = [-1,2,6,3,4,5,6] , head =[1,2,6,3,4,5,6]
2,while(-1.next != None):temp = [2,6,3,4,5,6] , head =[1,2,6,3,4,5,6],extraList = [-1,2,6,3,4,5,6]
3,while(2.next != None):temp = [3,4,5,6] , head =[1,2,6,4,5,6],extraList = [-1,2,3,4,5,6]
在这一步时,temp 表示 [存储2的结点],通过 temp.next=temp.next.next 将 [存储2的结点] 的 next指针跳过 6 ,指向 [存储3的结点] 。因此 [存储2的结点] 被改变了,所以 head 和 extraList 也被改变了。
4,以此类推,temp其实是改变了下一个结点为6的结点的next指针,并没有直接影响extraList ;但遍历 extraList 链表时会经过这些已经被改变的结点,所以 return extraList.next 就实现了删除结点。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。