題⽬描述

在⼀個排序的鏈表中，存在重複的結點，請刪除該鏈表中重複的結點，重複的結點不保留，返回鏈表頭指針。 例如，鏈表 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)