82. 删除排序链表中的重复元素 II

简介: 82. 删除排序链表中的重复元素 II

题目



image.png



思考


链表形态


本道题感觉是考验链表的基本知识。

链表形态

image.png

链表是一种存储非连续的存储结构,节点之前由指针链接构成。


相对于数组而言,链表方便增加 和 删除节点,但是对比数组不足的时,没办法做二分查找,因为链表不是通过下标寻址的,而是通过指针寻址的,这也是为什么会出现跳表数据结构,扯远了。。



如何删除节点


假设删除如下 【结点2】

image.png


定义三个指针,分别是 待删结点 / 上结点 和 下结点, 分别指向 结点2/结点1/结点3


image.png


只需要将 上结点 直接指向 下结点,然后将 待删节点删除即可

image.png


回归题目本身


需要删除重复的结点

和上面删除结点如出一辙,只不过有细微修改而已

image.png


如果我们像上图那样,找到上结点 下结点 和 待删除结点 ,这样就能够清理重复结点

我们怎么确定上结点 和 下结点?


只需要上节点的值 和 下节点一致,即可判断需要删除

伪代码

if 链表长度小于2
    直接返回链表
nextNode = head->next
下节点标记值
while (nextNode不等于NULL)
    if (nextNode节点 和 nextNode下一个节点不相等)
        if 下节点标记值
            直接从上节点 跳到 下节点即可
        else
            继续挪动链表
    else
        记录上节点值
        下节点标记值 = True
    nextNode = nextNode->next;
return 处理后的链表


代码提交

func deleteDuplicates(head *ListNode) *ListNode {
  currNode := head
    if currNode == nil {
        return head
    }
  nextNode := head.Next
  failedNode := head
  start := false
  rHead := new(ListNode)
  curr := rHead
  if nextNode == nil {
    return head
  }
  for nextNode != nil {
    if currNode.Val != nextNode.Val {
      if start {
        if failedNode.Val != currNode.Val {
          rNode := new(ListNode)
          rNode.Val = currNode.Val
          curr.Next = rNode
          curr = rNode
        }
      } else {
        rNode := new(ListNode)
        rNode.Val = currNode.Val
        curr.Next = rNode
        curr = rNode
      }
    } else {
      failedNode = currNode
      start = true
    }
    nextNode = nextNode.Next
    currNode = currNode.Next
  }
  if failedNode.Val != currNode.Val {
    rNode := new(ListNode)
    rNode.Val = currNode.Val
    curr.Next = rNode
    curr = rNode
  }
  return rHead.Next
}




难点和复杂点


感觉本题是考验对链表的基本操作


\


解题步骤,可以分为几步


  1. 单链表,如何删除一个节点
  2. 单链表,如何删除连续多个节点
  3. 根据条件(2节点数据相同),如何确认上结点 和 下结点
相关文章
|
2月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
01_移除链表元素
01_移除链表元素
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
3月前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
34 2
【数据结构OJ题】移除链表元素
|
2月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
21 0
|
2月前
|
Python
【Leetcode刷题Python】203.移除链表元素
文章提供了三种删除链表中特定值节点的方法:迭代法、虚拟节点迭代删除法和递归法,并给出了相应的Python实现代码。
17 0
|
3月前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
25 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表