欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

编码实现从无序链表中移除重复项(C和JAVA实例)

程序员文章站 2024-02-13 09:38:34
如果不能使用临时缓存,你怎么编码实现?复制代码 代码如下:方法一:不使用额外的存储空间,直接在原始链表上进行操作。首先用一个指针指向链表头节点开始,然后遍历其后面的节点,将...

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

复制代码 代码如下:

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

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