当前位置:   article > 正文

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

删除链表的重复元素
  • 标签:链表

题目描述

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

原题: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;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

说明:
代码中定义了一个链表节点类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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

说明:
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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

说明:
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
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

说明:
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版本
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;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
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);
    }
}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

说明
在上面的代码中,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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
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
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

复杂度分析

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

  • 时间复杂度: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个节点

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/850406
推荐阅读
相关标签
  

闽ICP备14008679号