数据结构和算法设计专题之—单链表中在指定的节点前面插入以及删除一个节点

数据结构和算法 尼古拉斯.赵四 6048℃ 0评论

题目:

在给定头结点的单链表中插入以及删除指定节点

这个题目我们遇到这个问题的时候可能会想这个该怎么解,我们知道如果在一个已知的节点之后添加和删除一个节点的话很容易的,那么如何在给定的节点之前插入一个节点以及删除指定节点?因为如果想删除和插入一个节点的话,肯定是需要获取前面的一个节点的,但是根据题目所给的条件中,我们可以看到我们是不可能获取到前面的一个节点的,所以得另外去想思路了,最后在编程之美中发现了这道题的解法,说实话,那真是很优雅的解决方案,而且很巧妙

1.在一个节点之前插入一个节点

思路如下:

假设我们想在节点P之前添加一个节点,如图所示:

那么我们可以这么做,将要插入的节点插入到节点P的后面,然后将节点P和节点Q的数据域进行交换,好一招偷龙转凤呀,

2.现在想删除节点P,我们也是没有P节点的前面的一个节点的,那么我们该怎么删除节点P呢?

思路如下:

我们可以将P节点后面的一个节点删除,然后将其中的数据域赋值到P节点中,这样就相当于P节点的删除了,也是使用的偷龙转凤技术

总结:

有时候想问题不能总是按照常规思路去想,解决这个问题最主要的技术:狸猫换太子

转载请注明:尼古拉斯.赵四 » 数据结构和算法设计专题之—单链表中在指定的节点前面插入以及删除一个节点

喜欢 (4)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址