当前位置:编程学习 > 网站相关 >>

[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;
      }
    }
 }
补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,