快捷導(dǎo)航

Java 數(shù)據(jù)結(jié)構(gòu)之刪除鏈表中重復(fù)的結(jié)點(diǎn)

更新時(shí)間：2021年12月11日 10:29:27 作者：2021dragon

在一個(gè)排序的鏈表中，會(huì)存在重復(fù)的結(jié)點(diǎn)，如何實(shí)現(xiàn)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，并返回鏈表頭指針呢？接下來(lái)小編將帶你詳細(xì)介紹

解析一：（不提倡）

解決該問題較簡(jiǎn)單，且在寫代碼時(shí)不易出錯(cuò)的做法如下：

遍歷一遍鏈表，記錄重復(fù)結(jié)點(diǎn)的結(jié)點(diǎn)值。
再遍歷一遍鏈表，逐個(gè)刪除重復(fù)結(jié)點(diǎn)。

動(dòng)圖演示：

該方法需要遍歷兩遍鏈表，且需要開辟額外的內(nèi)存空間存儲(chǔ)重復(fù)結(jié)點(diǎn)的結(jié)點(diǎn)值，所以一般不提倡。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == nullptr||pHead->next == nullptr) //鏈表為空或只有一個(gè)結(jié)點(diǎn)無(wú)需進(jìn)行操作
            return pHead;
        ListNode* cur = pHead;
        unordered_set<int> filter;
		//1、遍歷鏈表找出重復(fù)的結(jié)點(diǎn)，將結(jié)點(diǎn)值存入filter
		while (cur->next)
        {
			if (cur->val == cur->next->val)
				filter.insert(cur->val);
			cur = cur->next;
        }
		//2、逐個(gè)刪除重復(fù)的結(jié)點(diǎn)
        //先刪除頭部的重復(fù)結(jié)點(diǎn)
        while(pHead&&filter.find(pHead->val) != filter.end())
        {
            pHead = pHead->next;
        }
        if(pHead == nullptr)
            return nullptr;
        //再刪除其余的重復(fù)結(jié)點(diǎn)
        ListNode* prev = pHead;
        ListNode* last = prev->next;
        while(last)
        {
            if(filter.find(last->val) != filter.end())
            {
                prev->next = last->next;
                last = last->next;
            }
            else
            {
                prev = prev->next;
                last = last->next;
            }
        }
        return pHead; //返回鏈表頭指針
    }
};

解析二：（正解）

我們當(dāng)然應(yīng)該盡可能在遍歷一遍鏈表的情況下解決該問題，這時(shí)我們需要使用兩個(gè)指針配合完成，該過程當(dāng)中包含大量細(xì)節(jié)，大致步驟如下：

1.為了后續(xù)操作方便，先為該鏈表創(chuàng)建一個(gè)頭結(jié)點(diǎn)。

2.使用指針prev和last遍歷鏈表，初始時(shí)prev指向頭結(jié)點(diǎn)，last指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。

3.當(dāng)last指向的結(jié)點(diǎn)值與其后一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)值相同時(shí)，last獨(dú)自后移，直到last指向結(jié)點(diǎn)的結(jié)點(diǎn)值與其下一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)值不同為止，此時(shí)讓prev指向的結(jié)點(diǎn)指向last的后一個(gè)結(jié)點(diǎn)，最后讓last指向下一個(gè)結(jié)點(diǎn)（圖中未后移）。

4.當(dāng)last指向的結(jié)點(diǎn)值與其后一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)值不同時(shí)，prev和last一同向后移。

如此進(jìn)行下去，直到last將鏈表遍歷完，鏈表當(dāng)中重復(fù)的結(jié)點(diǎn)也就全部被刪除了，最后返回頭結(jié)點(diǎn)指向的鏈表即可。

動(dòng)圖演示：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};*/
class Solution {
public:
	ListNode* deleteDuplication(ListNode* pHead) {
		if (pHead == nullptr || pHead->next == nullptr) //鏈表為空或只有一個(gè)結(jié)點(diǎn)無(wú)需進(jìn)行操作
			return pHead;
		ListNode* head = new ListNode(0); //創(chuàng)建頭結(jié)點(diǎn)（便于操作）
		head->next = pHead; //頭結(jié)點(diǎn)與原鏈表建立關(guān)系
		ListNode* prev = head;
		ListNode* last = prev->next;
		while (last)
		{
			//未發(fā)現(xiàn)重復(fù)的結(jié)點(diǎn)，prev和last一同后移
			while (last->next&&last->val != last->next->val)
			{
				prev = prev->next;
				last = last->next;
			}
			//發(fā)現(xiàn)重復(fù)的結(jié)點(diǎn)，last獨(dú)自后移
			while (last->next&&last->val == last->next->val)
			{
				last = last->next;
			}
			//到達(dá)此處有三種情況：
			//1、沒有需要?jiǎng)h除的重復(fù)結(jié)點(diǎn)，是因?yàn)閘ast->next == nullptr到此
			//2、有需要?jiǎng)h除的重復(fù)結(jié)點(diǎn)，是因?yàn)閘ast->next == nullptr到此（鏈表后半段都需要?jiǎng)h除）
			//3、有需要?jiǎng)h除的重復(fù)結(jié)點(diǎn)，是因?yàn)閘ast->val != last->next->val到此（鏈表中間某段需要?jiǎng)h除）
			if (prev->next != last) //說明有需要?jiǎng)h除的重復(fù)結(jié)點(diǎn)
			{
				prev->next = last->next;
			}
			last = last->next;
		}
		return head->next; //返回鏈表頭指針
	}
};

到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)之刪除鏈表中重復(fù)的結(jié)點(diǎn)的文章就介紹到這了,更多相關(guān)Java 刪除鏈表重復(fù)結(jié)點(diǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: