2. 연결리스트 문제 해법

▶ 중복 없애기

정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.

 

필자는 Node 클래스를 따로 제작하여 이 문제를 풀기로 했다.

class Node {
	int data;
	Node next = null;
	
	Node(int d) {
		data = d;
	}
	
	//node 추가
	void append(int d) {
		Node end = new Node(d);
		Node n = this;
		while(n.next != null) {
			n = n.next;
		}
		n.next = end;
	}
}

 

다음은 중복을 없애기 위해 node 클래스 안에 원소들을 추적하여 없애는 방법을 선택했다.

prev는 앞서 설명했던 것 처럼 단방향일때 해당 지워야 하는 원소값을 찾을 경우 이전 노드와 다음 노드를 연결시키기만 해주면 된다.

void deleteDups(Node n) {
	// HashSet 제작, set은 중복을 없앨 수 있다.
	Set s = new HashSet();
		
	// prev는 삭제해야 할 노드를 찾았을 때 이전 노드와 다음 노드를 이어주기 위한 변수이다.
	Node prev = null;
		
	// 다음 노드가 null이 아니면 실행
	while(n.next != null) {
			
		// s안에 n의 데이터가 포함되어 있는지 여부 파악
		// 데이터가 포함되어 있을 경우 해당 값은 중복이므로 삭제시킬 수 있음(건너뛸 수 있음)
        	// 데이터가 포함되어 있지 않을 경우 해당 값은 이전에 나오지 않은 값이므로 set에 저장
		if(s.contains(n.data)) {
			//이전과 다음을 이어줌으로써 중간 노드를 없앰
			prev.next = n.next;
		} else {
			s.add(n.data);
			prev = n;
		}
		n = n.next;
	}
}

 

▶ 뒤에서 k번째 원소 구하기

단방향 연결리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라.

연결리스트의 길이를 아는 경우 맨 마지막 원소에서 k번째 원소는 length - k번째 원소가 되므로 단순히 연결리스트를 순회해서 이 원소를 찾으면 된다. 하지만 우리가 하는 것은 '연결리스트의 길이'를 모르는 경우이다.

책에서는 재귀적 방법으로 풀었지만, 내가 하는 방법을 우선적으로 소개하고, 책에서 자온 재귀적 방법을 소개하도록 하겠다.

int kThFromBehind(int k) {
		
	// head에 대한 객체를 저장한다.
	Node head = this;
	// n은 앞으로 k번째를 찾기 위해 값이 계속 변경될 객체이다.
	Node n = head;
	// count는 length와 같은 의미로 설계했다.
	int count = 0;
		
	// n이 null이 아닐 경우 노드의 연결형태로 계속 이어나가면서 count를 증가시킨다.
	while(n != null) {
		count++;
		n = n.next;
	}
		
	// 총 count에서 k만큼, 즉 뒤에서 k만큼 까지를 head에서부터 이동시킨다.
	for(int i = 0; i < count - k; i++) {
		head = head.next;
	}
		
	// head가 가리키고 있는 data를 반환한다.
	// 여기서 head는 실제 head가 아닌 뒤에서 k만큼 이동한 값이다.
	return head.data;
}

 

책에서 나온 재귀적 방법을 소개한다.

int printkThToLast(LinkedListNode head, int k) {
		
	// head가 null이면 return한다.
	if(head == null) {
		return 0;
	}
		
	// 재귀적 방법을 사용했다.
	// head의 다음 값과 k값을 넘기고 맨 마지막 호출되는 return 값은 0이다.
	// 계속 1씩 증가시키면서 결국 k와 같게 될 때 호출되고 index를 반환함으로써
	// if구문과 상관없게 만든다.
	int index = printKthToLast(head.next, k) + 1;
	if(index == k) {
		System.out.println(k + "th to last node is " + head.data);
	}
	return index;
}