[C.C.I] 02. 연결리스트

2.1 중복 없애기

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

연결리스트에서 중복되는 원소를 제거하기 위해서는 원소를 추적할 수 있어야 한다. 여기서는 해시 테이블을 사용해서 처리한다.

연결리스트를 순회하며 각 원소를 해시 테이블에 저장한다. 그러다가 중복된 원소를 발견하면, 그 원소를 제거한 후 계속 진행한다.

void deleteDups(LinkedListNode n) {
    HashSet set = new HashSet();
    LinkedListNode previous = null;
    while (n != null) {
        if (set.contains(n.data)) {
            previous.next = n.next;
        } else {
            set.add(n.data);
            previous = n;
        }
        n = n.next;
    }
}

위의 알고리즘은 O(N)이 걸린다.

 

2.4 분할

값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉, 원소 x는 '오른쪽 그룹' 어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다. (예제, 입력 : 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [분할 값 x=5], 출력 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8)

배열에서 원소 이동 비용은 비싸지만, 연결 리스트에서는 비교적 쉽다. 원소의 값을 이동(shift)하고 바꾸는(swap) 대신, 서로 다른 연결리스트 두 개를 만들면 된다. 하나에는 x보다 작은 원소들을 보관하고, 다른 하나에는 x보다 큰 원소들을 보관한다.

입력으로 주어진 연결리스트를 순회하면서, before 리스트 아니면 after 리스트에 원소를 삽입한다. 연결리스트의 마지막에 도달하면 분할 작업이 끝난 것이므로, before와 after를 합치면 된다.

이 방법은 분할 작업을 할 때 필요한 원소 이동이 없고 원소의 원래 순서를 유지할 수 있기 때문에 안정적(stable)이다.

// 연결 리스트의 헤드와 분할할 값을 인자로 넘겨준다.
LinkedListNode partition(LinkedListNode node, int x) {
    LinkedListNode beforeStart = null;
    LinkedListNode beforeEnd = null;
    LinkedListNode afterStart = null;
    LinkedListNode afterEnd = null;

    // 리스트를 분할한다.
    while (node != null) {
        LinkedListNode next = node.next;
        node.next = null;
        if (node.data < x) {
            // before 리스트의 끝에 원소를 삽입한다.
            if (beforeStart == null) {
                beforeStart = node;
                beforeEnd = beforeStart;
            } else {
                beforeEnd.next = node;
                beforeEnd = node;
            }
        } else {
            // after 리스트의 끝에 원소를 삽입한다.
            if (afterStart == null) {
                afterStart = node;
                afterEnd = afterStart;
            } else {
                afterEnd.next = node;
                afterEnd = node;
            }
        }
        node = next;
    }

    if (beforeStart == null) {
        return afterStart;
    }

    // before와 after를 병합한다.
    beforeEnd.next = afterStart;
    return beforeStart;
}

 

2.6 회문

주어진 연결리스트가 회문(palindrome)인지 검사하는 함수를 작성하라.

이 연결리스트는 앞에서 읽으나 뒤에서 읽으나 같아야 한다. 해법은 연결리스트를 뒤집은 다음 원래 리스트와 비교하는 것이다. 연결리스트가 회문이라면 두 리스트는 똑같을 것이다. 연결리스트를 뒤집어 비교할 때는 리스트의 절반만 비교하면 된다. 원래 리스트의 앞쪽 절반이 뒤집은 리스트의 앞쪽 절반과 같다면, 나머지 부분도 같을 것이다.

boolean isPalindrome(LinkedListNode head) {
	LinkedListNode reversed = reverseAndClone(head);
    return isEqual(head, reversed);
}

LinkedListNode reverseAndClone(LinkedListNode node) {
	LinkedListNode head = null;
    while (node != null) {
    	LinkedListNode n = new LinkedListNode(node.data); // 복사
        n.next = head;
        head = n;
        node = node.next;
    }
    return head;
}

boolean isEqual(LinkedListNode one, LinkedListNode two) {
	while (one != null && two != null) {
    	if (one.data != two.data) return false;
        one = one.next;
        two = two.next;
    }
    return one == null && two == null;
}

여기서 reverse와 isEqual 함수를 모듈화했다. 또한 head와 tail을 모두 반환할 수 있도록 클래스를 새로 만들었다. 

 

참고자료

<코딩 인터뷰 완전 분석> 게일 라크만 맥도웰 저, 프로그래밍 인사이트 출판