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

题⽬描述

在⼀个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
示例1
输⼊：{1,2,3,3,4,4,5}
返回值：{1,2,5}
思路及解答

hash统计

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

1. import java.util.HashMap;
3. public class Solution {
4.     public ListNode deleteDuplication(ListNode head) {
5.         if (head == null || head.next == null) {
6.             return head;
7.         }
8.         
9.         // 第一次遍历：统计每个节点值出现的次数
10.         HashMap<Integer, Integer> countMap = new HashMap<>();
11.         ListNode current = head;
12.         while (current != null) {
13.             countMap.put(current.val, countMap.getOrDefault(current.val, 0) + 1);
14.             current = current.next;
15.         }
16.         
17.         // 第二次遍历：删除重复节点
18.         ListNode dummy = new ListNode(-1); // 哑节点简化边界处理
19.         dummy.next = head;
20.         ListNode prev = dummy;
21.         current = head;
22.         
23.         while (current != null) {
24.             if (countMap.get(current.val) > 1) {
25.                 // 当前节点重复，跳过
26.                 prev.next = current.next;
27.             } else {
28.                 // 当前节点不重复，移动prev指针
29.                 prev = prev.next;
30.             }
31.             current = current.next;
32.         }
33.         
34.         return dummy.next;
35.     }
36. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(n)
  

直接遍历（推荐）

注意，题目已经提到是排序的节点，那么就可以直接原地删除
对⽐前后两个元素，如果相同的情况下，接着遍历后⾯的元素，直到元素不相等的时候，将前⾯的指针指向最后⼀个相同的元素的后⾯，相当于跳过了相同的元素。

1. public class Solution {
2.     public ListNode deleteDuplication(ListNode pHead)
3.     {
4.         //遍历链表，直接删除
5.         if(pHead == null || pHead.next == null) return pHead;
6.         ListNode head = new ListNode(0);
7.         head.next = pHead;
8.         ListNode cur = head.next;
9.         ListNode pre = head;
10.         while(cur != null){
11.             //将重复的结点都遍历过，然后将后面节点复制给pre结点后面
12.             if(cur.next != null && cur.val == cur.next.val){
13.                 while(cur.next != null &&  cur.val == cur.next.val){
14.                     cur = cur.next;
15.                 }
16.                 pre.next = cur.next;
17.                 cur = cur.next;
18.             }else{
19.                 pre = pre.next;
20.                 cur = cur.next;
21.             }
22.         }
23.         return head.next;
24.     }
25. }

复制代码

• 空间复杂度为 O(1) ，没有借助额外的空间
  
• 时间复杂度为 O(n) ，只遍历了⼀次链表
  

递归

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

1. /**
2. * 递归法：分治思想解决子问题
3. * 思路：将大问题分解为当前节点+剩余链表的子问题
4. *
5. */
6. public class Solution {
7.     public ListNode deleteDuplication(ListNode head) {
8.         // 递归终止条件：空链表或单节点链表
9.         if (head == null || head.next == null) {
10.             return head;
11.         }
12.         
13.         // 情况1：当前节点与下一节点重复
14.         if (head.val == head.next.val) {
15.             // 跳过所有重复节点，找到第一个不重复的节点
16.             ListNode node = head.next;
17.             while (node != null && head.val == node.val) {
18.                 node = node.next;
19.             }
20.             // 递归处理剩余部分
21.             return deleteDuplication(node);
22.         }
23.         // 情况2：当前节点不重复
24.         else {
25.             head.next = deleteDuplication(head.next);
26.             return head;
27.         }
28.     }
29. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(n) ，递归栈空间
  

三指针法

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

1. public class Solution {
2.     public ListNode deleteDuplication(ListNode head) {
3.         if (head == null || head.next == null) {
4.             return head;
5.         }
6.         
7.         ListNode dummy = new ListNode(-1);
8.         dummy.next = head;
9.         ListNode pre = dummy;    // 前驱指针
10.         ListNode cur = head;     // 当前指针
11.         ListNode next = null;     // 后继指针
12.         
13.         while (cur != null && cur.next != null) {
14.             next = cur.next;
15.             
16.             // 发现重复节点
17.             if (cur.val == next.val) {
18.                 // 移动next直到找到不重复的节点
19.                 while (next != null && cur.val == next.val) {
20.                     next = next.next;
21.                 }
22.                 // 跳过所有重复节点
23.                 pre.next = next;
24.                 cur = next;
25.             }
26.             // 没有重复，正常移动指针
27.             else {
28.                 pre = cur;
29.                 cur = cur.next;
30.             }
31.         }
32.         
33.         return dummy.next;
34.     }
35. }

复制代码

• 时间复杂度：O(n)
  
• 空间复杂度：O(1)
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！