迭代解法

首先一个比较「直观且通用」的思路是，采用「边遍历边构造」的方式：

  1. 建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面；
  2. 使用 tail 代表当前有效链表的结尾；
  3. 通过原输入的 pHead 指针进行链表扫描。

对原链表进行遍历，只要原链表尚未到达结尾，我们就重复如下决策（保留/跳过逻辑）：

  • 保留：pHead 已经没有下一个节点，pHead 可以被保留（插入到答案结尾指针 tail 后面）；pHead 有一下个节点，但是值与 pHead 不相同，pHead 可以被保留；
  • 跳过：当发现 pHead 与下一个节点值相同，需要对「连续相同一段」进行跳过。

举个 🌰，以题目示例 [1,2,3,3,4,4,5] 为例，使用图解的方式来感受一下。

  1. 「当前节点」与「下一节点」值不同，当前节点进行保留：    
  1. 「当前节点」与「下一节点」值相同，跳过「相同的连续一段」，当前节点不能保留：
代码： 
class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        # write code here
        dummy = ListNode(-1)
        tail = dummy
        while pHead != None:
            if pHead.next == None　or pHead.next.val != pHead.val:
                tail.next = pHead
                tail = pHead
                
            while pHead.next != None and pHead.val == pHead.next.val:
                pHead = pHead.next
            pHead = pHead.next

        tail.next =None
        return dummy.next
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

递归解法

递归解法相比于迭代解法，代码要简洁一些，但思维难度要高一些。

首先无论是否为“链表”类的题目，在实现递归前，都需要先明确「我们期望递归函数完成什么功能」，即设计好我们的递归函数签名。

显然，我们希望存在一个递归函数：传入链表头结点，对传入链表的重复元素进行删除，返回操作后的链表头结点。

该功能与题目要我们实现的 deleteDuplication 函数相同，因此我们直接使用原函数作为递归函数即可。

之后再考虑「递归出口」和「递归环节的最小操作」：

  • 递归出口：考虑什么情况下，我们不再需要「删除」操作。显然当传入的参数 pHead 为空，或者 pHead.next 为空时，必然不存在重复元素，可直接返回 pHead；
  • 递归环节的最小操作：之后再考虑删除逻辑该如何进行：
    • 显然，当 pHead.val != pHead.next.val 时，pHead 是可以被保留的，因此我们只需要将 pHead.next 传入递归函数，并将返回值作为 pHead.next，然后返回 pHead 即可；
    • 当 pHead.val == pHead.next.val 时，pHead 不能被保留，我们需要使用临时变量 tmp 跳过「与 pHead.val 值相同的连续一段」，将 tmp 传入递归函数所得的结果作为本次返回。

代码： 

class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        if pHead.val != pHead.next.val:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead
        else:
            tmp = pHead
            while tmp!=None and tmp.val == pHead.val:
                tmp =tmp.next
            return self.deleteDuplication(tmp)
  • 时间复杂度：O(n)
  • 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)


参考资料：