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

题⽬描述在⼀个排序的链表中存在重复的结点请删除该链表中重复的结点重复的结点不保留返回链表头指针。 例如链表 1-2-3-3-4-4-5 处理后为 1-2-5示例1输⼊{1,2,3,3,4,4,5}返回值{1,2,5}思路及解答hash统计第一次遍历统计频率第二次遍历删除重复节点javaimport java.util.HashMap; public class Solution { public ListNode deleteDuplication(ListNode head) { if (head null || head.next null) { return head; } // 第一次遍历统计每个节点值出现的次数 HashMapInteger, 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)直接遍历推荐注意题目已经提到是排序的节点那么就可以直接原地删除对⽐前后两个元素如果相同的情况下接着遍历后⾯的元素直到元素不相等的时候将前⾯的指针指向最后⼀个相同的元素的后⾯相当于跳过了相同的元素。javapublic 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) 只遍历了⼀次链表递归将大问题分解为当前节点剩余链表的子问题java/** * 递归法分治思想解决子问题 * 思路将大问题分解为当前节点剩余链表的子问题 * */ 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三个指针精确控制删除范围javapublic 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; }