Remove Duplicate from Unsorted List

先に説明したように,順序付けされたチェーンテーブルでノードを削除するには,チェーンテーブルを1回遍歴するだけであるため,時間的複雑度はO(n)である.この文章は無秩序チェーンテーブルの重み付け問題を議論する.
無秩序チェーンテーブルを与え,中の重複要素を削除し,bruce forceで行うと時間的複雑度はO(n^2)となり,等しい要素があれば現在のノードのnextを次のノードのnextに向けるとノードから判断する.各要素は、その後ろの要素を1回巡ります.コードは次のとおりです.

public ListNode deleteDuplicates(ListNode head) {
	if(head == null) return head;
	ListNode current = head;
	while(current != null) {
		int value = current.val;
		ListNode find = current;
		while(find.next != null) {
			if(find.next == value) {
				find.next = find.next.next;
			} else {
				find = find.next;
			}
		}
		current = current.next;
	}
	return head;
}

また、イベントの複雑さがO(n+nlogn)、すなわちO(nlogn)であるように、チェーンテーブルを集計ソートしてから、重量を除去することもできます.コードは次のとおりです.

public class DeleteDuplicate {
    public ListNode deleteDupli(ListNode head) {
        if(head == null) return null;

        ListNode helper = sort(head);
        while(head.next != null) {
            if(head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return helper;
    }

    public ListNode sort(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode a = sort(next);
        ListNode b = sort(head);
        return merge(a, b);
    }
        
    public ListNode merge(ListNode a, ListNode b) {
        if(a == null) return b;
        if(b == null) return a;
            
        if(a.val > b.val){
            b.next = merge(a, b.next);
            return b;
        } else {
            a.next= merge(a.next, b);
            return a;
        }             
     }
}