2. 연결리스트 문제 해법

▶ 중복 없애기

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

// 일반적으로 사용하는 노드를 우리의 실습환경에 맞게 재구성 했다.
class Node {
	int data;
	Node next = null;
	
	Node(int d) {
		data = d;
	}
	
	void append(int d) {
		Node end = new Node(d);
		Node n = this;
		while(n.next != null) {
			n = n.next;
		}
		n.next = end;
	}
	
    // 중복 제거 메소드
	void deleteDups(Node n) {
    
    	// Set의 장점은 데이터가 기억될 때에 순서를 저장하지 않는다는 점이다.
        // 즉, List와 Set의 차이 없이 분명히 두 개 모두 작동이 될 때에는,
        // 순서를 저장하지 않는 Set의 작동 시간이 우수하기 때문에 Set을 사용한다.
		Set s = new HashSet();
        
        // 현재 포인터가 가지고 있는 이전의 노드를 가리킨다.
		Node prev = null;
		while(n.next != null) {
        
        	// 만약 Set안에 현재 포인터 노드의 값이 포함되어 있다면
			if(s.contains(n.data)) {
            
            	// 이전 노드가 그 다음 노드랑 이어질 수 있도록 하라.
				prev.next = n.next;
			} else {
            
            	// 그렇지 않으면 Set에 데이터를 추가하고,
                // 이전의 Node는 prev를 통해 다시 구현된다.
				s.add(n.data);
				prev = n;
			}
			n = n.next;
		}
	}
}

 

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

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

int kThFromBehind(int d) {
	// 움직이지 않을 가장 고정적인 head를 지정한다.
	Node head = this;
	Node n = head;
	int count = 0;
    
    // 현재 자신이 가지고 있는 것이 없을 때 까지,
    // count는 반복적으로 증가시키고, n은 n.next를 따라가게 된다.
	while(n != null) {
		count++;
		n = n.next;
	}
    
    // 리스트의 node수에서 d만큼 빼면 head에서 얼만큼 가야 하는지에 대한 수가 나온다.
    // head를 이동시킨다.
	for(int i = 0; i < count - d; i++) {
		head = head.next;
	}
	return head.data;
}