Chapter 2 | Linked Lists--移除未排序連結清單中的重複項

2.1    Write code to remove duplicates from an unsorted linked list.

         FOLLOW UP，How would you solve this problem if a temporary buffer is not allowed?

譯文：從一個未排序的連結清單當中移除重複的項。進一步的，如果不允許使用臨時的緩存，你講如何解決這個問題？

又是移除重複項，有沒有一種似曾相識的感覺，不錯前面就讨論過判斷字元串的唯一性和字元串的去重，不過這裡不允許使用臨時的緩存(在後面會讨論可以使用臨時緩存的情況)，考慮連結清單的特性，我們就逐漸周遊，記錄下目前值，然後周遊後面的數，如果與記錄的值相同，則删除，直至周遊到連結清單尾。再然後從下一位置又進行新一輪的周遊，重複前面的操作，時間複雜度為O(n^2)。連結清單的一大優點就是添加删除元素簡單，這裡我們可以充分利用這一特點。預設為這是單向連結清單。代碼如下

/*把連結清單中後面的一次和前面的值比較，發現相同就删除*/
void removeduplicate(LINK_NODE* pHead)
{
	if (NULL == pHead)
		return;
	LINK_NODE *p, *q;
	LINK_NODE *c = pHead->next;

	while (c)
	{
		p = c;
		q = c->next;
		int value = c->data;
		while (q)
		{
			if (q->data == value)
			{
				LINK_NODE *t = q;
				p->next = q->next;
				q = p->next;
				delete t;
			}
			else
			{
				p = q;
				q = q->next;
			}
		}
		c = c->next;
	}
}
           

這裡假設大家對連結清單有足夠的了解，并且能夠自由編寫對外連結表這一資料結構，是以就直接貼局部代碼了。

如果允許使用臨時的緩存，那麼可沿用前面的思想，加以修改可達到我們的目的。下面給對外連結接

判斷字元串的唯一：http://blog.csdn.net/yeswenqian/article/details/16942185

字元串的去重(下半部分)：http://blog.csdn.net/yeswenqian/article/details/16951383

這裡我們讨論允許使用臨時緩存的情況，即可以借助額外的存儲空間，我們就開辟一個數組來儲存一個元素的出現情況，這裡不同的是，我們不知道這個連結清單中的資料類型是什麼，換言之，就是如果用一般數組來模拟的話，我們不知道需要開辟數組的空間大小以及是否能夠通過開辟一般數組來實作。假如連結清單中的資料類型是int型，包含負值，那麼這就不能像前面說的那樣的采用“數值代替位置”的情況來開辟數組了。最大值為32768，要是開辟一個這麼大的數組，勢必會浪費大量的空間。在這種情況下還沒糾結出一個很好的實作方法，哈希表是一個方法。

考慮到這是一道面試題，我們就采用哈希表來實作，暫時不考慮哈希表帶來的問題，即能将任意整數hash到一定範圍，不會出現下标為負值和hash鍵值沖突的情況。這裡采用的是常用的哈希表方式--“拉鍊法”，就是連結清單的數組

void removeduplicate(LINK_NODE* pHead)
{
	LINK_NODE *p = pHead->next;  //指向第一個資料節點
	LINK_NODE *q = p->next;
	memset(hash, 0, sizeof(hash));
	hash[p->data] = 1;   //置1，表示該數已經出現過
						 //第一個數肯定保留
	while (q != NULL)
	{
		if (hash[q->data])
		{
			LINK_NODE *t = q;
			p->next = q->next;
			q = p->next;
			delete t;
		}
		else
		{
			hash[q->data] = 1;
			p = q;      //q,p相鄰
			q = q->next;
		}
	}
}
           

如果考慮哈希表帶來的問題呢，比如鍵值沖突以及下标出現負值，這裡針對上面那種形式的哈希表談一下思路，對負值下标進行處理，取反比較友善，對于鍵值沖突，通過鍵值查找對應哈希表數組，然後再周遊該數組位置指向的連結清單，看是否有重複值。這樣處理在一定程度上減少了時間複雜度，也能夠處理由哈希表帶來的一些問題。