网站首页 全球最实用的IT互联网站!

人工智能P2P分享Wind搜索发布信息网站地图标签大全

当前位置:诺佳网 > 软件工程 > 后端开发 > Java >

剑指offer-56、删除链表中重复的节点

时间:2025-12-30 09:00

人气:

作者:admin

标签:

导读:题⽬描述 在⼀个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 1-gt;2-gt;3-gt;3-gt;4-gt;4-gt;5 处理后为 1-gt;2-gt;5 示例1 输⼊...

题⽬描述

在⼀个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表 1->2->3->3->4->4->5 处理后为 1->2->5

示例1
输⼊:{1,2,3,3,4,4,5}
返回值:{1,2,5}

思路及解答

hash统计

第一次遍历统计频率,第二次遍历删除重复节点

import java.util.HashMap;

public class Solution {
    public ListNode deleteDuplication(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 第一次遍历:统计每个节点值出现的次数
        HashMap<Integer, Integer> countMap = new HashMap<>();
        ListNode current = head;
        while (current != null) {
            countMap.put(current.val, countMap.getOrDefault(current.val, 0) + 1);
            current = current.next;
        }
        
        // 第二次遍历:删除重复节点
        ListNode dummy = new ListNode(-1); // 哑节点简化边界处理
        dummy.next = head;
        ListNode prev = dummy;
        current = head;
        
        while (current != null) {
            if (countMap.get(current.val) > 1) {
                // 当前节点重复,跳过
                prev.next = current.next;
            } else {
                // 当前节点不重复,移动prev指针
                prev = prev.next;
            }
            current = current.next;
        }
        
        return dummy.next;
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

直接遍历(推荐)

注意,题目已经提到是排序的节点,那么就可以直接原地删除

对⽐前后两个元素,如果相同的情况下,接着遍历后⾯的元素,直到元素不相等的时候,将前⾯的指针指向最后⼀个相同的元素的后⾯,相当于跳过了相同的元素。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        //遍历链表,直接删除
        if(pHead == null || pHead.next == null) return pHead;
        ListNode head = new ListNode(0);
        head.next = pHead;
        ListNode cur = head.next;
        ListNode pre = head;
        while(cur != null){
            //将重复的结点都遍历过,然后将后面节点复制给pre结点后面
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null &&  cur.val == cur.next.val){
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = pre.next;
                cur = cur.next;
            }
        }
        return head.next;
    }
}
  • 空间复杂度为 O(1) ,没有借助额外的空间
  • 时间复杂度为 O(n) ,只遍历了⼀次链表

递归

将大问题分解为当前节点+剩余链表的子问题

/**
 * 递归法:分治思想解决子问题
 * 思路:将大问题分解为当前节点+剩余链表的子问题
 * 
 */
public class Solution {
    public ListNode deleteDuplication(ListNode head) {
        // 递归终止条件:空链表或单节点链表
        if (head == null || head.next == null) {
            return head;
        }
        
        // 情况1:当前节点与下一节点重复
        if (head.val == head.next.val) {
            // 跳过所有重复节点,找到第一个不重复的节点
            ListNode node = head.next;
            while (node != null && head.val == node.val) {
                node = node.next;
            }
            // 递归处理剩余部分
            return deleteDuplication(node);
        } 
        // 情况2:当前节点不重复
        else {
            head.next = deleteDuplication(head.next);
            return head;
        }
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n) ,递归栈空间

三指针法

使用pre、cur、next三个指针精确控制删除范围

public class Solution {
    public ListNode deleteDuplication(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;    // 前驱指针
        ListNode cur = head;     // 当前指针
        ListNode next = null;     // 后继指针
        
        while (cur != null && cur.next != null) {
            next = cur.next;
            
            // 发现重复节点
            if (cur.val == next.val) {
                // 移动next直到找到不重复的节点
                while (next != null && cur.val == next.val) {
                    next = next.next;
                }
                // 跳过所有重复节点
                pre.next = next;
                cur = next;
            } 
            // 没有重复,正常移动指针
            else {
                pre = cur;
                cur = cur.next;
            }
        }
        
        return dummy.next;
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

本文来自在线网站:seven的菜鸟成长之路,作者:seven,转载请注明原文链接:www.seven97.top

温馨提示:以上内容整理于网络,仅供参考,如果对您有帮助,留下您的阅读感言吧!
相关阅读
本类排行
相关标签
本类推荐

CPU | 内存 | 硬盘 | 显卡 | 显示器 | 主板 | 电源 | 键鼠 | 网站地图

Copyright © 2025-2035 诺佳网 版权所有 备案号:赣ICP备2025066733号
本站资料均来源互联网收集整理,作品版权归作者所有,如果侵犯了您的版权,请跟我们联系。

关注微信