- 标签：链表
题目描述
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
原题：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;
}
// 最后一个不重复元素后面应该为null
slow.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 = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow = head
fast = head.next
while fast:
if slow.val != fast.val:
slow.next = fast
slow = slow.next
fast = fast.next
slow.next = None
return head
说明：
Python版本的实现中，使用了类定义链表节点，并实现了deleteDuplicates方法。与Java和C语言版本的逻辑相同。
Golang版本
package main
import "fmt"
// 定义链表节点
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
slow := head
fast := head.Next
for fast != nil {
if slow.Val != fast.Val {
slow.Next = fast
slow = slow.Next
}
fast = fast.Next
}
slow.Next = nil
return head
}
func main() {
// 示例链表: 1->1->2
head:= &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, val=0, next=None):
self.val = val
self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
if head.val == head.next.val:
return self.deleteDuplicates(head.next)
else:
head.next = self.deleteDuplicates(head.next)
return head
Golang版本
type ListNode struct {
Val int
Next *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个节点 |
这些题目涉及到了链表、数组的基本操作，包括删除重复项、合并、查找特定节点等，对于理解链表和数组的基本数据结构以及操作非常有帮助。通过解决这些相似题目，可以加深对链表和数组操作的理解，并提升编程技能。
