递归，迭代在链表中的运用

青旅半醒 2022-11-13 07:29 205阅读 0赞

[82\_删除链表中的重复节点2][82_2]

[83\_删除链表中的重复节点1][83_1]

这两道题的不同点是，82要求删除重复的节点，83式要求保留自身，删除与自身相同的节点。

# 递归 #

### 对于82题 ###

递归结束的条件是与当前节点不同的下一个节点，将重复节点的下一个不一样节点进行递归

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70][]

class Solution(object):
        def deleteDuplicates(self, head):
            if not head or not head.next:
                return head
            if head.val != head.next.val:
                head.next = self.deleteDuplicates(head.next)
            else:
                move = head.next
                while move and head.val == move.val:
                    move = move.next
                return self.deleteDuplicates(move)
            return head

### 对于83题 ###

因为保留自身，停止递归的条件是当前节点和当前的下下个节点比较，将当前节点的下一个节点进行递归

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1][]

class Solution(object):
        def deleteDuplicates(self, head):
            if not head or not head.next:
                return head
            if head.val != head.next.val:
                head.next = self.deleteDuplicates(head.next)
            else:
                move = head.next
                while move.next and head.val == move.next.val:
                    move = move.next
                return self.deleteDuplicates(move)
            return head

# 迭代 #

### 对于82题 ###

代码中用到了一个常用的技巧：dummy 节点，也叫做 哑节点。它在链表的迭代写法中非常常见，因为对于本题而言，我们可能会删除头结点 head，为了维护一个不变的头节点，所以我们添加了 dummy，让dummy.next = head，这样即使 head 被删了，那么会操作 dummy.next 指向新的链表头部，所以最终返回的也是 dummy.next。

class Solution(object):
        def deleteDuplicates(self, head):
            if not head or not head.next:
                return head
            dummy = ListNode(0)
            dummy.next = head
            pre = dummy
            cur = head
            while cur:
                # 跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                if pre.next == cur:
                     # pre和cur之间没有重复节点，pre后移
                    pre = pre.next
                else:
                    # pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
                    # 但是pre不移动，仍然指向已经遍历的链表结尾
                    pre.next = cur.next
                cur = cur.next
            return dummy.next

### 对于83题 ###

使用两个指针 pre 和 cur：pre 节点表示固定一个节点，cur 用于寻找所有跟 pre 值相等的节点。如果 cur.val 等于 pre.val，则删除 cur。在找到不等的 val 之前，pre 不走，只移动 cur。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2][]

class Solution(object):
        def deleteDuplicates(self, head):
            if not head: return None
            prev, cur = head, head.next
            while cur:
                if cur.val == prev.val:
                    prev.next = cur.next
                else:
                    prev = cur
                cur = cur.next
            return head

# 83——单个节点进行迭代 #

![a72609cbba7bb03d1c6144c46e087d32.png][]

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def deleteDuplicates(self, head):
            #利用两个指针
            if not head: return None
            cur = head
            while cur.next:
                if cur.val == cur.next.val:
                    cur.next = cur.next.next
                else:
                   cur = cur.next
            return head

# 哑节点 #

### 对于82题 ###

基本思路

> 几乎所有的链表题目，都具有相似的解题思路。
> 
> 建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
> 
> 使用 tail 代表当前有效链表的结尾
> 
> 通过原输入的 head 指针进行链表扫描
> 
> 我们会确保「进入外层循环时 head 不会与上一节点相同」，因此插入时机：
> 
> head 已经没有下一个节点，head 可以被插入
> 
> head 有一下个节点，但是值与 head 不相同，head 可以被插入

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            tail = dummy = ListNode(-1)
            while head:
                if head.next == None or head.val != head.next.val:
                    tail.next = head;
                    tail = head
                while head.next and head.val == head.next.val:
                    head = head.next
                head = head.next
            tail.next = None
            return dummy.next

### 对于83题 ###

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

class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            if head == None:
                return None
            dummy = ListNode(-101)
            tail = dummy
            while head:
                if tail.val != head.val:
                    tail.next = head;
                    tail = tail.next
                head = head.next
            tail.next = None
            return dummy.next

[82_2]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
[83_1]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221022/5cb9c12c04094bce95f41bfaa130e44b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: /images/20221022/91fa47ffc6244efbbc38d74d60011d27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]: /images/20221022/fe9f165f29824c29b651ac1a243b86ab.png
[a72609cbba7bb03d1c6144c46e087d32.png]: /images/20221022/4ce6742d7f064b268446df286eca39e5.png