创建asp.net网站,微信开放平台是干嘛的,西宁网站设计,杭州网站制作标签#xff1a;链表
题目描述
给定一个排序链表#xff0c;删除所有重复的元素#xff0c;使得每个元素只出现一次。
原题#xff1a;LeetCode 83
思路及实现
方式一#xff1a;双指针
思路
使用快慢双指针遍历链表#xff0c;快指针用于遍历链表#xff0c;慢指…标签链表
题目描述
给定一个排序链表删除所有重复的元素使得每个元素只出现一次。
原题LeetCode 83
思路及实现
方式一双指针
思路
使用快慢双指针遍历链表快指针用于遍历链表慢指针用于指向不重复元素的最后一个位置。当快指针指向的元素与慢指针指向的元素不同时将慢指针向后移动一位并将快指针指向的元素赋值给慢指针指向的位置。这样可以保证慢指针之前的元素都是不重复的。
代码实现
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, val0, nextNone):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函数进行处理最后遍历结果链表并打印。 方式二递归
在处理链表删除重复元素的问题时通过递归的方式能够简洁地表达算法逻辑。以下是方式二的详细解释和示例代码。
思路
对于递归方法我们需要定义一个递归函数该函数接受链表的头节点作为参数并返回处理后的链表的头节点。递归函数的主要任务是判断当前节点是否与其下一个节点重复并据此决定是继续递归还是删除下一个节点。 基本情况如果链表为空head null或只有一个节点head.next null则没有重复元素可删除直接返回头节点。 递归情况 如果当前节点head的值与其下一个节点head.next的值相同说明有重复元素我们需要删除下一个节点。递归调用deleteDuplicates函数处理head.next并返回处理后的头节点此时原head节点将被忽略因为重复。如果当前节点head的值与其下一个节点head.next的值不同说明没有重复元素我们保留head节点并递归处理head.next。将处理后的head.next赋值给head.next并返回head。
代码实现
以下是使用递归方法删除链表重复元素的示例代码分别用Java、Python和Golang实现。
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, val0, nextNone):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 headGolang版本
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个节点
这些题目涉及到了链表、数组的基本操作包括删除重复项、合并、查找特定节点等对于理解链表和数组的基本数据结构以及操作非常有帮助。通过解决这些相似题目可以加深对链表和数组操作的理解并提升编程技能。
