Java 數(shù)據(jù)結構之刪除鏈表中重復的結點

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

在一個排序的鏈表中，會存在重復的結點，如何實現(xiàn)刪除該鏈表中重復的結點，重復的結點不保留，并返回鏈表頭指針呢？接下來小編將帶你詳細介紹

解析一：（不提倡）

解決該問題較簡單，且在寫代碼時不易出錯的做法如下：

遍歷一遍鏈表，記錄重復結點的結點值。
再遍歷一遍鏈表，逐個刪除重復結點。

動圖演示：

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

/*
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) //鏈表為空或只有一個結點無需進行操作
            return pHead;
        ListNode* cur = pHead;
        unordered_set<int> filter;
		//1、遍歷鏈表找出重復的結點，將結點值存入filter
		while (cur->next)
        {
			if (cur->val == cur->next->val)
				filter.insert(cur->val);
			cur = cur->next;
        }
		//2、逐個刪除重復的結點
        //先刪除頭部的重復結點
        while(pHead&&filter.find(pHead->val) != filter.end())
        {
            pHead = pHead->next;
        }
        if(pHead == nullptr)
            return nullptr;
        //再刪除其余的重復結點
        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; //返回鏈表頭指針
    }
};

解析二：（正解）

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

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

2.使用指針prev和last遍歷鏈表，初始時prev指向頭結點，last指向頭結點的下一個結點。

3.當last指向的結點值與其后一個結點的結點值相同時，last獨自后移，直到last指向結點的結點值與其下一個結點的結點值不同為止，此時讓prev指向的結點指向last的后一個結點，最后讓last指向下一個結點（圖中未后移）。

4.當last指向的結點值與其后一個結點的結點值不同時，prev和last一同向后移。

如此進行下去，直到last將鏈表遍歷完，鏈表當中重復的結點也就全部被刪除了，最后返回頭結點指向的鏈表即可。

動圖演示：

/*
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) //鏈表為空或只有一個結點無需進行操作
			return pHead;
		ListNode* head = new ListNode(0); //創(chuàng)建頭結點（便于操作）
		head->next = pHead; //頭結點與原鏈表建立關系
		ListNode* prev = head;
		ListNode* last = prev->next;
		while (last)
		{
			//未發(fā)現(xiàn)重復的結點，prev和last一同后移
			while (last->next&&last->val != last->next->val)
			{
				prev = prev->next;
				last = last->next;
			}
			//發(fā)現(xiàn)重復的結點，last獨自后移
			while (last->next&&last->val == last->next->val)
			{
				last = last->next;
			}
			//到達此處有三種情況：
			//1、沒有需要刪除的重復結點，是因為last->next == nullptr到此
			//2、有需要刪除的重復結點，是因為last->next == nullptr到此（鏈表后半段都需要刪除）
			//3、有需要刪除的重復結點，是因為last->val != last->next->val到此（鏈表中間某段需要刪除）
			if (prev->next != last) //說明有需要刪除的重復結點
			{
				prev->next = last->next;
			}
			last = last->next;
		}
		return head->next; //返回鏈表頭指針
	}
};

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

您可能感興趣的文章: