データ構造 〜 第2章 連結リスト 問題2-1

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

問題2-1.

ソートされていない連結リストから、重複する要素を削除する。

下記方法で書いた。

１．再帰
２．HashMapを使用して、登場済みの数字を記憶しておく。

1.再帰を使ったコード。

public Node deleteDuplicatedNode(Node head){
		if(head == null){
			return head;
		}
		
		int tmp = head.data;
		Node node = head;
		while(node.next != null){
			if(node.next.data == tmp){
				head = head.next;
				return deleteDuplicatedNode(head);
			}
			node = node.next;
		}
		return head;
	}

Nodeクラス。

package intro.linkedList;

public class Node {
	public Node next = null;
	public int data;
	
	public Node(int d){
		data = d;
	}
	
	//ノードの追加
	public void appendToTail(int d){
		Node end = new Node(d);
		Node node = this;
		while(node.next != null){
			node = node.next;
		}
		node.next = end;
	}
	
	//特定の値を保持するノード削除する
	public Node deleteNode(Node head, int d){
		Node node = head;
		
		if(node.data == d){
			//先頭が削除対象の場合、先頭を次のノードに変更する
			return head.next;
		}
		
		while(node.next != null){
			if(node.next.data == d){
				node.next = node.next.next;
				return head;
			}
			node = node.next;
		}
		
		return node;
	}
	
	//特定の値を保持するノードを削除する
	public Node deleteNode(int d){
		Node node = this;
		
		if(node.data == d){
			//先頭が削除対象の場合、先頭を次のノードに変更する
			return this.next;
		}
		
		while(node.next != null){
			if(node.next.data == d){
				node.next = node.next.next;
				return this;
			}
			node = node.next;
		}
		
		return this;
	}
	
	//ソートされていない連結リストから重複する要素を削除するメソッド
	public Node deleteDuplicatedNode(Node head){
		if(head == null){
			return head;
		}
		
		int tmp = head.data;
		Node node = head;
		while(node.next != null){
			if(node.next.data == tmp){
				head = head.next;
				return deleteDuplicatedNode(head);
			}
			node = node.next;
		}
		return head;
	}
	
}

確認用。

package problem2_1;

import intro.linkedList.Node;

public class Solve2_1 {

	public static void main(String[] args) {
		Node node1 = new Node(1);
		node1.appendToTail(2);
		node1.appendToTail(3);
		node1.appendToTail(4);
		node1.appendToTail(5);
		node1.appendToTail(4);
		node1.appendToTail(3);
		node1.appendToTail(2);
		node1.appendToTail(1);
	
		
		Node node = node1;
		while(node != null){
			System.out.println(node.data);
			node = node.next;
		}
		System.out.println("**********");
		
		node = node1;
		Node tmpNode = node.deleteDuplicatedNode(node);
		while(tmpNode != null){
			System.out.println(tmpNode.data);
			tmpNode = tmpNode.next;
		}
	}
	
}

２．HashMapを使用する方法

//ソートされていない連結リストから重複する要素を削除するメソッド
	public Node deleteDuplicatedNode1(Node head){
		HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
		
		Node node = head;
		Node before = head;
		while(node != null){
			if(map.containsKey(node.data)){
				before.next = node.next;
			}else{
				map.put(node.data, true);
				before = node;
			}
			node = node.next;
		}
		return head;
	}