[google口试CTCI] 2-1.移除链表中重复元素

2013-10-22

[google面试CTCI] 2-1.移除链表中重复元素【链表】Q:Write code to remove duplicates from an unsorted lin

[google面试CTCI] 2-1.移除链表中重复元素

【链表】

Q: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?

题目：编码实现从无序链表中移除重复项。

如果不能使用临时缓存，你怎么编码实现？

解答：

方法一：不使用额外的存储空间，直接在原始链表上进行操作。首先用一个指针指向链表头节点开始，然后遍历其后面的节点，将与该指针所指节点数据相同的节点删除。然后将该指针后移一位，继续上述操作。直到该指针移到链表。

void delete_duplicate1(node* head){
    node*pPos=head->next;
    node*p,*q;
    while(pPos!=NULL){//用pPos指针来指示当前移动到什么位置了
        p=pPos;
       q=pPos->next;
       while(q!=NULL){//遍历pPos后面的所有节点，找出节点值与pPos所指节点相同的节点，将其删除
            if(pPos->data==q->data){
                node*pDel=q;
                p->next=q->next;
                q=p->next;
                free(pDel);
                }
            else{
                p=q;
                q=q->next;
                }
            }
        pPos=pPos->next;
        }
}

方法二：如果允许使用额外的空间，则能通过空间换时间，来降低算法的复制度。可以使用hash表来完成，既然是面试题，我们这里可以暂时先不考虑使用hash可能带来的一些问题，先假设它是完美的。即假设它能将任意整数hash到一定范围，不会出现负数下标，不会出现hash冲突等。

void delete_duplicate2(node* head)
{
    node*p=head->next;
    node*q=p->next;
    memset(hash,0,sizeof(hash));
    hash[p->data]=1;//置为1，表示该数已经出现过
    while(q!=NULL){
        if(hash[q->data]!=0){
            node*pDel=q;
            p->next=q->next;
            q=p->next;
            free(pDel);
            }
        else{
            hash[q->data]=1;//置为1，表示该数已经出现过
            p=q;
            q=q->next;
            }
        }
}

JAVA参考代码：

public static void deleteDups(LinkedListNode n) {  Hashtable table = new Hashtable();  LinkedListNode previous = null;  while (n != null) {    if (table.containsKey(n.data)) previous.next = n.next;    else {      table.put(n.data, true);      previous = n;    }    n = n.next;  }}

public static void deleteDups2(LinkedListNode head) {    if (head == null) return;    LinkedListNode previous = head;    LinkedListNode current = previous.next;    while (current != null) {      LinkedListNode runner = head;      while (runner != current) { // Check for earlier dups        if (runner.data == current.data) {          LinkedListNode tmp = current.next; // remove current          previous.next = tmp;           current = tmp; // update current to next node          break; // all other dups have already been removed        }        runner = runner.next;      }      if (runner == current) { // current not updated - update now        previous = current;        current = current.next;      }    } }

作者：Viidiot 微信公众号：linux-code

热点排行

编程

[google口试CTCI] 2-1.移除链表中重复元素