코딩 인터뷰 완전분석 - 연결 리스트(Linked list)

특징

• 삽입, 삭제가 O(1)시간에 가능하다는 장점
• 조회에는 O(n)의 선형시간 (최악의 경우)
• 단방향, 양방향 연결 리스트 가능
• 해시 테이블의 chaining 기법은 해싱한 한 Key에 대해 value 리스트(여러 value)를 갖는데, 연결리스트를 이용하는 것

Runner 기법

: current 노드를 가리키는 포인터와, current부터 tail 노드까지 순회하는 포인터로 구성. 기본적으로 알고리즘 작성 시 O(N^2)

여러가지 연결리스트 문제

중간 노드 삭제

: n1은 next를 찾아가고, n2는 next의 next(두번 점프)를 찾아가도록 구성하면 n2가 tail에 다다른 시점에 n1은 리스트의 가운데 노드를 가리키게 되는 것을 이용

• slow runner, fast runner

두 연결리스트의 합

// (7 -> 1 -> 6) + (5 -> 9 -> 6) // 2 -> 1 -> 9 // 즉, 912

// 재귀를 이용하는 방법
Node addList(Node* n1, Node* n2, int carry) {
  if(n1 == NULL && n2 == NULL && carry == 0) {
    return NULL;
  }
  
  Node* node = new Node();
  
  node.data += carry;
  node.data += n1 == NULL ? 0 : n1.data;
  node.data += n2 == NULL ? 0 : n2.data;
  
  carry = node.data / 10;
  node.data %= 10;
  
  node.next = addList(
    n1 == NULL ? NULL : n1.next,
    n2 == NULL ? NULL : n2.next,
    carry == 0 ? 0 : 1
  );
  
  return node;
}

// 순서를 반대로 한 경우
struct prevResult {
  Node* node = NULL;
  int carry = 0;
};

prevResult getPrevResult(Node* n1, Node* n2) { bnm
  if(n1 == NULL && n2 == NULL) {
    return new prevResult();
  }
  
  prevResult* prevNode = getPrevResult(
    n1.next == NULL ? NULL : n1.next,
    n2.next == NULL ? NULL : n2.next
  );
  
  Node* cur = new Node();
  cur.data += prevNode.carry;
  cur.data += n1 != NULL ? n1.data : 0;
  cur.data += n2 != NULL ? n2.data : 0;
  
  int carry = cur.data /= 10;
  cur.data %= 10;
  
  cur.next = prevNode.node;
  
  prevResult curResult = new prevNode();
  curResult.node = cur;
  curResult.carry = carry;
  
  return curResult;
}

Node getResult(Node* head1, Node* head2) {
  prevResult* headResult = getPrevResult(head1, head2);
  
  return headResult;
}

연결리스트가 팰린드롬인지 확인하기

// #1 stack 사용 - reverse 방향을 스택에 쌓기
stack<char> reversed;

void stackReversed(Node* cur) {
  if(cur.next == NULL) {
    return;
  }
  reversed.push(cur.data);
  stackReversed(cur.next);
  return;
}

bool isPalindrome(Node* head) {
  stackReversed(head);
  
  int size = reversed.size();
  Node* left = head;
  while(size / 2 == reversed.size()) {
    char rightData = reversed.top();
    reversed.pop();
    
    if(left.data != rightData) {
      return false;
    }
  }
  
  return true;
}

// #2 역방향 연결리스트 만들기
Node* getReversed(Node& cur) {
  if(cur.next == NULL) {
    return cur;
  }
  
  Node node = new Node();
  node.next = getReversed(cur);
  return node;
}

bool isPalindrome(Node* head) {
  Node* tail = getReversed(head);
  
  // 길이를 알면 절반만 순회하도록 개선 가능
  while(tail != NULL && head != NULL) {
    if(tail.data != head.data) {
      return false;
    }
  }
  
  return true;
}

두 연결리스트의 교집합

: 두 연결리스트가 합쳐지는 어떤 접점노드가 있다는 뜻

• 방법 1. 모든 노드(주소값)를 해시에 넣어 중복값이 있는 것을 확인하기
• 방법 2. 두 리스트를 단순히 조회해서 tail이 같은 노드인지를 확인

연결리스트에 루프 존재유무 판별하기

• 방법 1. 주소값을 해시에 넣어 이미 조회한 노드인지를 확인
• 방법 2(책 해법). slow runner와 fast runner를 돌려 충돌하는지를 확인
  • 건너뛰지 않을까 생각했지만, 직접 시나리오를 생각해보면 그런 경우는 존재하지 않는다.

Reference)

코딩 인터뷰 완전분석