[면접 스터디] 선형자료구조2

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)이가 소요된다.

  	```java
  		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;
    }