【LeetCode】第15天 - 83. 删除排序链表中的重复元素 | 82. 删除排序链表中的重复元素 II

简介: 83. 删除排序链表中的重复元素 | 82. 删除排序链表中的重复元素 II

题目描述

题目1(83. 删除排序链表中的重复元素)

在这里插入图片描述

题目2(82. 删除排序链表中的重复元素 II)

在这里插入图片描述

解题思路

题目1(83. 删除排序链表中的重复元素)

使用指针pre遍历链表,比较当前 pre.val与 pre.next.val是否相同,如果相同则删除pre.next节点(pre.next = pre.next.next)。

题目2(82. 删除排序链表中的重复元素 II)

  • 使用三个指针(left,mid,right)遍历链表,如果mid.val与left.val和right.val都不相等,则将mid节点插入到新链表的链尾。
  • 对于第一个节点,只需要比较它与第二个节点的元素是否相同,如果不同,则将第一个节点插入到新链表的链尾。
  • 同理,对于最后一个节点,只需要比较它与倒数第二个节点的元素是否相同,如果不同,则将最后一个节点插入到新链表的链尾。
    在这里插入图片描述

代码实现

题目1(83. 删除排序链表中的重复元素)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
    public ListNode deleteDuplicates(ListNode head) {
   
        //链表为空或只有一个节点时,直接返回head
        if (head == null || head.next == null) {
   
            return head;
        }

        ListNode pre = head;
        while (pre.next != null) {
   
            if (pre.val == pre.next.val) {
   
                pre.next = pre.next.next;    //删除pre.next指针
            } else {
   
                pre = pre.next;
            }
        }

        return head;
    }
}

题目2(82. 删除排序链表中的重复元素 II)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
    public ListNode deleteDuplicates(ListNode head) {
   
            //链表为空或只有一个节点时,直接返回head
        if(head == null || head.next == null) return head;
        //链表只有两个节点时,只需比较前两个节点
        if(head.next.next == null){
   
            if(head.val == head.next.val) return null;
            else return head;
        }
        ListNode res = new ListNode(0);
        ListNode temp = res;
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //针对第一个和第二个节点的比较
        if(head.val != head.next.val){
   
            temp.next = head;
            temp = head;
        }
        while(right != null){
   
            if(mid.val != left.val && mid.val != right.val){
   
                temp.next = mid;
                temp = mid;
            }
            left = left.next;
            mid = mid.next;
            right = right.next;
        }
        //遍历结束时,mid和left就分别指向最后一个和倒数第二个节点
        //针对最后一个和倒数第二个节点的比较
        if(mid.val != left.val){
   
            temp.next = mid;
            temp = mid;
        }
        temp.next = null;

        return res.next;
    }
}
目录
相关文章
|
3月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
46 1
|
3月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
60 0
Leetcode第21题(合并两个有序链表)
|
3月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
48 0
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
30 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
34 0
LeetCode第二十四题(两两交换链表中的节点)
|
3月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
50 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
3月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
112 0
|
4月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
5月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
69 6
|
5月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
137 2