题目
思考
链表形态
本道题感觉是考验链表的基本知识。
链表形态
链表是一种存储非连续的存储结构，节点之前由指针链接构成。
相对于数组而言，链表方便增加 和 删除节点，但是对比数组不足的时，没办法做二分查找，因为链表不是通过下标寻址的，而是通过指针寻址的，这也是为什么会出现跳表数据结构，扯远了。。
如何删除节点
假设删除如下 【结点2】
定义三个指针，分别是 待删结点 / 上结点 和 下结点， 分别指向 结点2/结点1/结点3
只需要将 上结点 直接指向 下结点，然后将 待删节点删除即可
回归题目本身
需要删除重复的结点
和上面删除结点如出一辙，只不过有细微修改而已
如果我们像上图那样，找到上结点 下结点 和 待删除结点 ，这样就能够清理重复结点
我们怎么确定上结点 和 下结点？
只需要上节点的值 和 下节点一致，即可判断需要删除
伪代码
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 }
难点和复杂点
感觉本题是考验对链表的基本操作
\
解题步骤，可以分为几步
- 单链表，如何删除一个节点
- 单链表，如何删除连续多个节点
- 根据条件(2节点数据相同)，如何确认上结点 和 下结点
