【程式員面試金典】 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​​