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

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


代码如下:

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

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

赞 (0)

相关推荐

  • Java实现双向链表(两个版本)

    临近春节,项目都结束了,都等着回家过年了.下面是小编给大家研究数据结构的相关知识,链表算是经常用到的一种数据结构了,现将自己的实现展示如下,欢迎大神赐教. 第一个版本,没有最后一个节点,每次从根节点开始遍历 public class LinkedList<E> { private Node head; public LinkedList() { } public E getFirst(){ if(head==null){ return null; } return head.value; }

  • java实现单链表之逆序

    下面一段代码准确的介绍了java实现单链表逆序,具体内容就不做详解了,有需要的朋友可以直接拷贝了 package com.ckw.mianshi; /** * java 实现单链表的逆序 * @author Administrator * */ public class SingleLinkedReverse { class Node{ int data; Node next; public Node(int data){ this.data = data; } } public static

  • Java模拟有序链表数据结构的示例

    有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择 优先级队列 可以使用有序链表来实现 有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,

  • Java语言中链表和双向链表

    链表是一种重要的数据结构,在程序设计中占有很重要的地位.C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构.Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点. class Node { Object data; Node next;//指向下一个结点 } 将数据域定义成Object类是因为

  • java实现数据结构单链表示例(java单链表)

    复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类  E data; // 节点上的数据  Node<E> next; // 指向下一个节点 Node(E e) {   this.data = e;   this.next = null;  } } private Node<E> head; // 链表的头节点 private N

  • java双向循环链表的实现代码

    例1: 复制代码 代码如下: package com.xlst.util; import java.util.HashMap;import java.util.Map;import java.util.UUID; /*** 双向循环链表* 完成时间:2012.9.28* 版本1.0* @author xlst**/public class BothwayLoopLinked {/*** 存放链表长度的 map* * 如果简单使用 static int 型的 size 基本类型变量,则只能维护一个

  • java中使用双向链表实现贪吃蛇程序源码分享

    使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(

  • java实现单链表、双向链表

    本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {

  • Java采用循环链表结构求解约瑟夫问题

    本文实例讲述了Java采用循环链表结构求解约瑟夫问题的方法.分享给大家供大家参考.具体分析如下: 这是第一次java考试的试题,对于没看过链表的同学来说就不会做,现在回头看看,还真不难. 约瑟夫问题: 有n个人,其编号分别为1,2,3,-,n.这n个人按顺序排成一个圈.现在给定s和d,从第s个人开始从1依次报数,数到d的人出列,然后又从下一个人开始又从1开始依次报数,数到d的人又出列,如此循环,直到最后所有人出列为止.要求定义一个节点类,采用循环链表结构求解约瑟夫问题. 以下java版的答案:

  • Java模拟单链表和双端链表数据结构的实例讲解

    Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1．集合中必存在唯一的一个"第一元素": 2．集合中必存在唯一的一个 "最后元素" : 3．除最后一个元素之外,均有 唯一的后继(后件):

随机推荐