1. 정렬되어 있지 않은 링크드리스트에서 중복된 원소를 없애라

  • 임시 버퍼를 사용 할 수 있을 때
    링크드리스트를 순회하면서, Hash 테이블에 저장 Hash 테이블에 이미 저장된 데이터라면 삭제한다. 시간복잡도는 O(n)이 소요된다.

          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;
           }
  • 임시 버퍼를 사용 할 수 없을 때
    버퍼가 없다면 두 개의 포인터를 사용해 문제를 해결 할 수 있다. 현재 포인터와 runner 포인터를 이용해 중복을 제거 할 수 있다. 시간복잡도는 O(N^2)이가 소요된다.

          void deleteDups(LinkedListNode head){
            LinkedListNode current = head;
    
            while(current != null){
              LinkedListNode runner = current;
              while(runner.next != null){
                if(runner.next.data == current.data){
                  runner.next = runner.next.next;
                } else{
                  runner = runner.next;
                }
              }
              current = current.next;
            }
          }

    2. 주어진 링크드리스트가 Palindrome인지 Stack을 이용해 검사하는 방법을 설명하라

    두개의 포인터를 이용한다. 하나의 포인터 slow는 한칸 씩 이동하면서 stack에 쌓는다. runner 포인터는 두칸 씩 이동한다. runner 포인터가 끝 부분에 닿으면 stack에는 링크드리스트 절반의 노드가 역순으로 stack에 쌓여있다. 이후부터 stack의 top과 slow를 한칸 씩 이동하면서 비교한다.

      boolean isPalindrome(LinkedListNode head){
        LinkedListNode fast = head;
        LinkedListNode slow = head;
        Stack stack = new Stack();
    
        // 리스트 앞 절반을 스택에 쌓는다.
        while(fast != null or fast.next != null) {
          stack.push(slow.data);
          slow = slow.next;
          fast = fast.next.next;
        }
    
        // node 수가 홀수 개라면 가운데 원소는 넘긴다
        if (fast != null) {
          slow = slow.next;
        }
    
        while(slow != null) {
          int top = stack.pop().intValue();
          if(top != slow.data) {
            return false;
          }
          slow = slow.next;
        }
        return true;
      }

3. LRU를 stack으로 어떻게 구현 할 수 있는지 설명하라

빼고자 하는 임의 값이 나오기 전까지 새로운 Stack을 만들어 저장한다. 빼고자 하는 값을 pop 한 뒤, 새로운 stack의 값들을 하나씩 pop하면서 원래의 stack으로 옮긴다. 그리고 뺀 데이터를 다시 stack에 push한다.

또는 double linked list를 이용해 구현 할 수 있다. 빼고자 하는 Stack의 node까지 찾아간 다음, 해당 노드를 제거하고 head 앞에 넣어준다.

    void moveMidToHead(Node node){
      Node preNode = node.preNode;
      Node nextNode = node.nextNode;

      if(preNode != null) {
        preNode.nextNode = nextNode;
      }

      if(next != null) {
        nextNode.preNode = preNode;
      } else {
          this.tailNode = nextNode;
      }

      this.headNode = node;
    }