【数据结构与算法 | 基础篇】[链表专题]力扣82

简介: 【数据结构与算法 | 基础篇】[链表专题]力扣82

1. 力扣82 : 删除排序链表中的重复元素

题 :

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
 
 
 
示例 1:
 
 
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
示例 2:
 
 
输入:head = [1,1,1,2,3]
输出:[2,3]
 
 
提示:
 
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列1. 给定一个已排

思路1 : 递归法


  • 标准开头,如果head为空链表或该链表只有一个节点,直接返回.
  • 如果head指向的节点的数据域与其下一个节点的数据域相等,则p记录head的下下一个节点.p节点仍然有可能与head节点的数据域相等.while循环.如果p的数据域与head的数据域相等,则将head后移一个节点.如果不相等,则跳出循环.因为p之前的节点按照规则都需要删除.所以需要返回p的节点的递归结果.
  • 如果head指向的节点的数据域与下一个节点的数据域不想等,则head连接head的下一个节点的递归结果.并返回head.

解1 :

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            ListNode p = head.next.next;
            while (p != null) {
                if (p.val == head.val) {
                    p = p.next;
                } else {
                    break;
                }
            }
            return deleteDuplicates(p);
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

思路2 : 一次遍历(官方题解)


  • 头节点有可能被删除,所以设置哨兵节点dummy.cur被初始化指向哨兵节点.问题变为判断cur.next与cur.next.next是否需要删除.第一次循环时,判断第一个节点的数据域是否与第二个节点相等,如果相等,p指向第二个节点的next节点.如果p为null,cur.next指向null.如果不相等,判断p节点的数据域是否与cur.next的数据域相等,如果相等,则指向的该节点也需要删除,即p=p.next.如果不想等,退出内层循环,cur.next指向p.(如出现1 2 2 2 3这种情况).
  • 当最后一次while循环时,此时cur指向链表的倒第三个节点.判断cur.next的数据域是否与cur.next.next的相等.如果相等,p为null.则cur.next=null.如果不想等,倒第一和二的节点无需删除.cur=cur.next.while条件不满足.退出循环.

解2 :

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(10086, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                ListNode p = cur.next.next.next;
                while (p != null) {
                    if (p.val == cur.next.val) {
                        p = p.next;
                    } else {
                        break;
                    }
                }
                cur.next = p;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}
相关文章
|
21小时前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
8 2
|
21小时前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
5 0
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
3天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
3天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
3天前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
3天前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)