LeetCode题解 83. 删除排序链表中的重复元素

文章目录

• LeetCode题解 83. 删除排序链表中的重复元素
• • 题目描述
  • 题解
  • • 迭代写法
    • 递归写法

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例一:
输入: 1->1->2
输出: 1->2


示例二:
输入: 1->1->2->3->3
输出: 1->2->3

题解

迭代写法

解题思路

1. 用cur表示当前节点，利用wile循环遍历链表
2. 结束条件为: 遍历完链表，即 cur.next 为空; 
             头结点 head 可能为空, 则也需要判断 cur 是否为空
3. 遍历过程中：
	(1)如果该节点出元素与下一节点元素相同，
	   则删除下一节点: cur.next = cur.next.next;
	(2)若不同，则继续遍历;

细节分析

1. 需要判断 head 是否为空:
	(1) 可在开头判断 head 是否为空
	(2) 也可在 while 循环中判断 cur 是否为空
2. 为什么如果前后两节点元素相同，删除后节点，而不用 cur = cur.next 操作？
答：是因为删除该节点的下一节点，该节点仍需要和新的下一节点进行比较

代码

• java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        //cur != null 的作用是判断 head 是否为 null
        while (cur != null && cur.next != null) {
            if (cur.next.val == cur.val) {
                //删除cur.next节点
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

• c++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        while (cur != NULL && cur->next != NULL) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }

        return head;
    }
};

• python

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else: cur = cur.next

        return head

递归写法

解题思路

* 递归写法的删除节点操作是 通过返回下一节点 连接到上一节点，
* 来实现参数节点(即当前节点)的删除

递归的三步法:
(参数 head 的含义为当前节点)

1. 终止条件: 遍历完链表
	(1) head.next 为空
	(2) head 为空，即空链表
2. 终止处理: 返回当前节点
3. 提取重复逻辑:
	(1) 节点的"连接": 利用函数返回值作为下一节点
	(2) 节点的"删除": 判断是否当前节点元素与下一节点元素是否相同, 返回相应的节点

代码

• java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        head.next = deleteDuplicates(head.next);

        return head.val == head.next.val ? head.next : head;
    }
}

• c++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }

        head->next = deleteDuplicates(head->next);

        return head->val == head->next->val ? head->next : head;
    }        
};

• python

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        head.next = self.deleteDuplicates(head.next)

        return head.next if head.val == head.next.val else head

LeetCode传送门: 83. 删除排序链表中的重复元素
题解传送门: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/solution/83-die-dai-he-di-gui-liang-chong-xie-fa-a3lch/

本文地址：https://blog.csdn.net/qq_45538657/article/details/110941072