【程序员面试金典】 02.01 移除重复节点-摩杜云开发者社区

1 题目

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

2 题解

利用桶排序的方式

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RemoveDuplicateNodes(ListNode head) {
        bool[] bucket = new bool[20001];
        int[] res = new int[20001];

        for (int i=0; i<20001; i++)
        {
            bucket[i] = false;
        }

        int n=0;

        if (head == null) return null;

        do {
            if (bucket[head.val]==false)
            {
                bucket[head.val]=true;
                res[n]=head.val;
                n++;
            }
            head = head.next;
        }while(head!=null);

        ListNode resf = new ListNode();
        ListNode nnex = new ListNode();

        nnex=resf;
        for (int i=0; i<n; i++)
        {
            resf.next = new ListNode(res[i]);
            resf = resf.next;
        }
        return nnex.next;
    }
}

3 知识点

链表

内存地址不连续，数据分散存储

每个数据元素（数据域，首元节点）都配备一个指针（指针域）

如果链表有头节点，头指针指向头节点，否则，头指针指向首元节点。

头节点和头指针的区别：

头节点是一个节点，包含数据域和指针域；头指针是一个指针，只声明，没有分配内存。

链表中可以没有头节点，但是不能没有头指针。

数组&链表：

数组需要先定义长度，不能适用于动态增减；

链表可以动态分配内存。

数据的增删上来看，链表的效率高于数组；

从数据的访问来看，链表的效率低于数组。

所以如果是需要快速访问，很少插入、删除数组的情况下，可以使用数组。

如果是经常需要插入和删除元素，就可以使用链表。

桶排序

参考文章：

https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.runoob.com/w3cnote/bucket-sort.html