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;
		}
	}
}
           

如果考虑哈希表带来的问题呢，比如键值冲突以及下标出现负值，这里针对上面那种形式的哈希表谈一下思路，对负值下标进行处理，取反比较方便，对于键值冲突，通过键值查找对应哈希表数组，然后再遍历该数组位置指向的链表，看是否有重复值。这样处理在一定程度上减少了时间复杂度，也能够处理由哈希表带来的一些问题。