Java 數據結構之刪除鏈表中重復的結點

Posted on by

核心考點：鏈表操作，臨界條件檢查，特殊情況處理

在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。

解析一：（不提倡）

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

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

動圖演示：

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

/*
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; //返回鏈表頭指針
    }
};

解析二：（正解）

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

1.為瞭後續操作方便，先為該鏈表創建一個頭結點。

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); //創建頭結點（便於操作）
		head->next = pHead; //頭結點與原鏈表建立關系
		ListNode* prev = head;
		ListNode* last = prev->next;
		while (last)
		{
			//未發現重復的結點，prev和last一同後移
			while (last->next&&last->val != last->next->val)
			{
				prev = prev->next;
				last = last->next;
			}
			//發現重復的結點，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 數據結構之刪除鏈表中重復的結點的文章就介紹到這瞭,更多相關Java 刪除鏈表重復結點內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：