赞
踩
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
原题:LeetCode 83
使用快慢双指针遍历链表,快指针用于遍历链表,慢指针用于指向不重复元素的最后一个位置。当快指针指向的元素与慢指针指向的元素不同时,将慢指针向后移动一位,并将快指针指向的元素赋值给慢指针指向的位置。这样可以保证慢指针之前的元素都是不重复的。
// 定义链表节点 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
,返回头节点。
// 定义链表节点 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版本类似,只是语法上有所差异。
# 定义链表节点 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语言版本的逻辑相同。
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实现。
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语言实现删除排序链表中重复元素的递归解法:
#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
函数用于释放链表占用的内存。
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
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) | O(1) |
方式二(递归) | 代码简洁,逻辑清晰 | 递归深度可能导致栈溢出,内存占用不稳定 | O(n) | O(n) |
以下是一些与删除排序链表中重复元素问题相似的题目:
相似题目 | 难度 | 链接 |
---|---|---|
删除排序数组中的重复项 | 简单 | 力扣:26. 删除排序数组中的重复项 |
删除排序数组中的重复项 II | 中等 | 力扣:80. 删除排序数组中的重复项 II |
删除链表中的节点 | 容易 | 力扣:237. 删除链表中的节点 |
移除链表元素 | 简单 | 力扣:203. 移除链表元素 |
合并两个有序链表 | 简单 | 力扣:21. 合并两个有序链表 |
链表中倒数第k个节点 | 中等 | 力扣:19. 链表中倒数第k个节点 |
这些题目涉及到了链表、数组的基本操作,包括删除重复项、合并、查找特定节点等,对于理解链表和数组的基本数据结构以及操作非常有帮助。通过解决这些相似题目,可以加深对链表和数组操作的理解,并提升编程技能。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。