【剑指 の 精选】详解「删除链表中重复结点」的两种解法 ｜Python 主题月

输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}
复制代码

class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (pHead != null) {
            // 进入循环时，确保了 pHead 不会与上一节点相同
            if (pHead.next == null || pHead.next.val != pHead.val) {
                tail.next = pHead;
                tail = pHead;
            }
            // 如果 pHead 与下一节点相同，跳过相同节点（到达「连续相同一段」的最后一位）
            while (pHead.next != null && pHead.val == pHead.next.val) pHead = pHead.next;
            pHead = pHead.next;
        }
        tail.next = null;
        return dummy.next;
    }
}
复制代码

class Solution:
    def deleteDuplication(self, pHead):
        dummy = ListNode(-1)
        tail = dummy
        while pHead is not None:
            # 进入循环时，确保了 pHead 不会与上一节点相同
            if pHead.next is None or pHead.next.val != pHead.val:
                tail.next = pHead
                tail = pHead
            # 如果 pHead 与下一节点相同，跳过相同节点（到达「连续相同一段」的最后一位）
            while pHead.next is not None and pHead.val == pHead.next.val:
                pHead = pHead.next
            pHead = pHead.next
        tail.next = None
        return dummy.next
复制代码

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        // 递归出口：当「输入节点为空」或者「不存在下一节点」，直接返回
        if (pHead == null || pHead.next == null) return pHead;
        if (pHead.val != pHead.next.val) {
            // 若「当前节点」与「下一节点」值不同，则当前节点可以被保留
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        } else {
            // 若「当前节点」与「下一节点」相同，需要跳过「值相同的连续一段」
            ListNode tmp = pHead;
            while (tmp != null && tmp.val == pHead.val) tmp = tmp.next;
            return deleteDuplication(tmp);
        }
    }
}
复制代码

class Solution:
    def deleteDuplication(self, pHead):
        # 递归出口：当「输入节点为空」或者「不存在下一节点」，直接返回
        if pHead is None or pHead.next is None:
            return pHead
        if pHead.val != pHead.next.val:
            # 若「当前节点」与「下一节点」值不同，则当前节点可以被保留
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead
        else:
            # 若「当前节点」与「下一节点」相同，需要跳过「值相同的连续一段」
            tmp = pHead
            while tmp is not None and tmp.val == pHead.val:
                tmp = tmp.next
            return self.deleteDuplication(tmp)
复制代码

class Solution {
    public ListNode deleteDuplication(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}
复制代码

class Solution:
    def deleteDuplication(self, pHead):
        if pHead is None:
            return pHead
        dummy = ListNode(-109)
        tail = dummy
        while pHead is not None:
            # 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if tail.val != pHead.val:
                tail.next = pHead
                tail = tail.next
            pHead = pHead.next
        tail.next = None
        return dummy.next
复制代码