【经典算法】Leetcode.83删除排序链表中的重复元素(Java/C/Python3/Go实现含注释说明,Easy)

server/2024/11/14 6:48:50/

题目描述

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

原题:LeetCode 83

思路及实现

方式一:双指针

思路

使用快慢双指针遍历链表,快指针用于遍历链表,慢指针用于指向不重复元素的最后一个位置。当快指针指向的元素与慢指针指向的元素不同时,将慢指针向后移动一位,并将快指针指向的元素赋值给慢指针指向的位置。这样可以保证慢指针之前的元素都是不重复的。

代码实现

Java版本
java">// 定义链表节点
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}ListNode slow = head;ListNode fast = head.next;while (fast != null) {if (slow.val != fast.val) {slow.next = fast;slow = slow.next;}fast = fast.next;}// 最后一个不重复元素后面应该为nullslow.next = null;return head;}
}

说明:
代码中定义了一个链表节点类ListNode,并在Solution类中实现了deleteDuplicates方法。首先判断链表是否为空或只有一个节点,若是则直接返回。然后初始化快慢指针,快指针指向头节点的下一个节点。在循环中,当快慢指针指向的元素不同时,将慢指针的next指向快指针,并将慢指针向后移动一位。最后,将最后一个不重复元素的next置为null,返回头节点。

C语言版本
// 定义链表节点
struct ListNode {int val;struct ListNode *next;
};struct ListNode* deleteDuplicates(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head;}struct ListNode *slow = head;struct ListNode *fast = head->next;while (fast != NULL) {if (slow->val != fast->val) {slow->next = fast;slow = slow->next;}fast = fast->next;}slow->next = NULL;return head;
}

说明:
C语言版本的实现与Java版本类似,只是语法上有所差异。

Python3版本
# 定义链表节点
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:if not head or not head.next:return headslow = headfast = head.nextwhile fast:if slow.val != fast.val:slow.next = fastslow = slow.nextfast = fast.nextslow.next = Nonereturn head

说明:
Python版本的实现中,使用了类定义链表节点,并实现了deleteDuplicates方法。与Java和C语言版本的逻辑相同。

Golang版本
package mainimport "fmt"// 定义链表节点
type ListNode struct {Val  intNext *ListNode
}func deleteDuplicates(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}slow := headfast := head.Nextfor fast != nil {if slow.Val != fast.Val {slow.Next = fastslow = slow.Next}fast = fast.Next}slow.Next = nilreturn head
}func main() {// 示例链表: 1->1->2head:= &ListNode{Val: 1}head.Next = &ListNode{Val: 1}head.Next.Next = &ListNode{Val: 2}result := deleteDuplicates(head)// 打印结果链表for result != nil {fmt.Print(result.Val, " ")result = result.Next}
}

说明:
Golang版本的实现中,首先定义了一个ListNode结构体来表示链表节点。然后在deleteDuplicates函数中实现了删除重复元素的功能。最后,在main函数中创建了一个示例链表,并调用deleteDuplicates函数进行处理,最后遍历结果链表并打印。

方式二(递归)

在处理链表删除重复元素的问题时,通过递归的方式能够简洁地表达算法逻辑。以下是方式二的详细解释和示例代码。

思路

对于递归方法,我们需要定义一个递归函数,该函数接受链表的头节点作为参数,并返回处理后的链表的头节点。递归函数的主要任务是判断当前节点是否与其下一个节点重复,并据此决定是继续递归还是删除下一个节点。

  1. 基本情况:如果链表为空(head == null)或只有一个节点(head.next == null),则没有重复元素可删除,直接返回头节点。

  2. 递归情况

    • 如果当前节点head的值与其下一个节点head.next的值相同,说明有重复元素,我们需要删除下一个节点。递归调用deleteDuplicates函数处理head.next,并返回处理后的头节点,此时原head节点将被忽略(因为重复)。
    • 如果当前节点head的值与其下一个节点head.next的值不同,说明没有重复元素,我们保留head节点,并递归处理head.next。将处理后的head.next赋值给head.next,并返回head

代码实现

以下是使用递归方法删除链表重复元素的示例代码,分别用Java、Python和Golang实现。

Java版本
java">public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null) {return head;}if (head.val == head.next.val) {return deleteDuplicates(head.next);} else {head.next = deleteDuplicates(head.next);return head;}}
}
C语言

下面是使用C语言实现删除排序链表中重复元素的递归解法:

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct ListNode {int val;struct ListNode *next;
} ListNode;// 创建新节点
ListNode* createNode(int val) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 递归删除重复元素
ListNode* deleteDuplicates(ListNode* head) {// 基本情况:空链表或只有一个节点,没有重复元素if (head == NULL || head->next == NULL) {return head;}// 如果头节点和下一个节点值相同,递归删除下一个节点if (head->val == head->next->val) {return deleteDuplicates(head->next);}// 如果头节点和下一个节点值不同,递归处理下一个节点,并更新头节点的next指针else {head->next = deleteDuplicates(head->next);return head;}
}// 打印链表
void printList(ListNode* head) {ListNode* current = head;while (current != NULL) {printf("%d ", current->val);current = current->next;}printf("\n");
}// 释放链表内存
void freeList(ListNode* head) {ListNode* current = head;while (current != NULL) {ListNode* temp = current;current = current->next;free(temp);}
}
}

说明
在上面的代码中,createNode 函数用于创建新链表节点,deleteDuplicates 函数是递归删除重复元素的实现,printList 函数用于打印链表freeList 函数用于释放链表占用的内存。

Python3版本
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:if not head or not head.next:return headif head.val == head.next.val:return self.deleteDuplicates(head.next)else:head.next = self.deleteDuplicates(head.next)return head
Golang版本
type ListNode struct {Val  intNext *ListNode
}func deleteDuplicates(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}if head.Val == head.Next.Val {return deleteDuplicates(head.Next)} else {head.Next = deleteDuplicates(head.Next)return head}
}

复杂度分析

对于递归解法,复杂度分析需要考虑递归调用的次数和递归过程中使用的额外空间。

  • 时间复杂度:O(n),其中n是链表的长度。每个节点最多被访问一次,因此时间复杂度是线性的。
  • 空间复杂度:O(n),其中n是链表的长度。在最坏情况下,当链表中所有节点都重复时,递归的深度将达到n,因此需要额外的栈空间来存储递归调用信息。

总结

以下是针对删除排序链表中重复元素问题的不同方式的对比总结:

方式优点缺点时间复杂度空间复杂度
方式一(双指针迭代)不使用递归,内存占用稳定代码相对复杂,需要处理边界情况O(n)O(1)
方式二(递归)代码简洁,逻辑清晰递归深度可能导致栈溢出,内存占用不稳定O(n)O(n)

相似题目

以下是一些与删除排序链表中重复元素问题相似的题目:

相似题目难度链接
删除排序数组中的重复项简单力扣:26. 删除排序数组中的重复项
删除排序数组中的重复项 II中等力扣:80. 删除排序数组中的重复项 II
删除链表中的节点容易力扣:237. 删除链表中的节点
移除链表元素简单力扣:203. 移除链表元素
合并两个有序链表简单力扣:21. 合并两个有序链表
链表中倒数第k个节点中等力扣:19. 链表中倒数第k个节点

这些题目涉及到了链表、数组的基本操作,包括删除重复项、合并、查找特定节点等,对于理解链表和数组的基本数据结构以及操作非常有帮助。通过解决这些相似题目,可以加深对链表和数组操作的理解,并提升编程技能。


http://www.ppmy.cn/server/29882.html

相关文章

【笔记】Python3|2024年 PDF 转 XML 或 HTML 的第三方库的使用方式、测评过程以及对比结果(汇总)

文章目录 PDF2HTML_Samples1 测评过程2 评估方式3 结果说明4 测评列表 PDF2HTML_Samples 目的是对比一下常用的 PDF 转 HTML/XML 的工具。 整个对比过程放在了 Github 仓库中&#xff0c; 欢迎提交 PR/Issue 补充更多工具&#xff1a;https://github.com/shandianchengzi/PDF…

构建矿业企业数字化未来:核心架构与落地策略

随着数字化时代的到来&#xff0c;矿业企业正面临着前所未有的机遇与挑战。在这个充满变革的时代&#xff0c;构建一个稳固的数字化核心架构并将其有效落地成为了矿业企业持续发展的关键。本文将深入探讨矿业企业数字化核心架构的构建和落地策略&#xff0c;助您在数字化转型的…

PHP的数组练习实验

实 验 目 的 掌握索引和关联数组&#xff0c;以及下标和元素概念&#xff1b; 掌握数组创建、初始化&#xff0c;以及元素添加、删除、修改操作&#xff1b; 掌握foreach作用、语法、执行过程和使用&#xff1b; 能应用数组输出表格和数据。 任务1&#xff1a;使用一维索引数…

SQLite如何处理CSV 虚拟表(三十七)

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLite的DBSTAT 虚拟表&#xff08;三十六&#xff09; 下一篇:SQLite的扩展函数Carray()表值函数(三十八) ​ RFC4180格式是一种文本文件格式&#xff0c;被用于表格数据间的交互&#xff0c;也可将表格数据转化…

Mybatis高级

1. Mybatis多表查询概念 ​ 在学习多表查询的之前&#xff0c;我们要先明确多表的关系都有哪些&#xff0c;如何划分。 1.1 多表关系的划分 一对一 一对一的关系是两张表之间 A表的一条数据只能对应B表的一条数据。比如 订单表和用户表 一个订单只能属于…

【Node.js工程师养成计划】之express框架

一、Express 官网&#xff1a;http://www.expressjs.com.cn express 是一个基于内置核心 http 模块的&#xff0c;一个第三方的包&#xff0c;专注于 web 服务器的构建。 Express 是一个简洁而灵活的 node.js Web应用框架, 提供了一系列强大特性帮助你创建各种 Web 应用&…

CogAgent:开创性的VLM在GUI理解和自动化任务中的突破

尽管LLMs如ChatGPT在撰写电子邮件等任务上能够提供帮助&#xff0c;它们在理解和与GUIs交互方面存在挑战&#xff0c;这限制了它们在提高自动化水平方面的潜力。数字世界中的自主代理是许多现代人梦寐以求的理想助手。这些代理能够根据用户输入的任务描述自动完成如在线预订票务…

SQL 基础 | AS 的用法介绍

SQL&#xff08;Structured Query Language&#xff09;是一种用于管理和操作数据库的标准编程语言。 在SQL中&#xff0c;AS关键字有几种不同的用法&#xff0c;主要用于重命名表、列或者查询结果。 以下是AS的一些常见用法&#xff1a; 重命名列&#xff1a;在SELECT语句中&a…