[Coding Interview] 연결리스트 관련 문제

 

문제 : 단방향 연결리스트에서, 뒤에서 k번째 원소를 찾아라. 길이는 미리 주어지지 않는다.   조건 : 추가적인 buffer 는 사용하지 못한다.   첫번째 풀이 : 모두 순회하여 길이를 알아낸 다음, root 에서 길이-k 만큼 다시 이동하여 찾는다. 공간 복잡도는 O(1) 이지만 시간 복잡도는 O(N) 이다.   두번째 풀이 : 재귀적인 방법을 사용한다. 마치 stack 처럼 첫번째부터 재귀적으로 파고 들어간다. 마지막 원소를 만나면 0을 return 하고 그 뒤부터는 계속 return+1 을 return 한다. 그렇게 되면 뒤에서 k번째 원소의 값은 알 수 있지만 원소 자체(주소)는 알 수 없게된다. 어떻게 풀어나가야 할까? 여러 방법이 있다. static 변수를 사용하여 count 해나가도 좋고, counter 와 원소값을 갖는 class 를 하나 만들어서 return 해도 좋다. 공간 복잡도는 재귀함수를 N번 사용하기 때문에 O(N) 이고, 시간 복잡도는 O(N) 이다.   세번째 풀이 : 더 "이거다!" 싶은 풀이법이다.  index를 두 개 준다. i1, i2라고 하자. i1은 k만큼 먼저 출발하고, 그 뒤로 i2가 i1과 똑같이 속도로 k만큼 떨어져서 함께 연결 리스트를 이동하게 한다. 그럼 i1이 마지막에 도달했을 때 i2는 i1과 k 만큼 떨어져있기 때문에, 뒤에서 k 번째 원소에 머물에 된다. 공간 복잡도는 O(1) 이고, 시간 복잡도는 O(N)이다.

 

문제 : 단방향 연결 리스트의 한 노드 주소값을 알고 있을 때, 그 노드만 삭제하는 코드를 작성하라.   조건 : head 에 접근은 불가능하다.   풀이 : 우리는 head 에 접근할 수 없다. 그럼 어떻게 해당 노드의 before 와 next를 이어지게 만들 수 있을까? next 노드의 값을 삭제할 노드로 복사한 뒤, next 노드를 지우면 된다. 예를 들어 다음과 같은 수도 코드처럼 하면 된다.   Node deleteNode; //삭제해야 하는 노드. if( deleteNode.next == null ) return false; //다음 노드가 없으면 안 된다. if( deleteNode == null ) return false; // 삭제해야 할 노드가 없으면 안 된다. Node nextNode = deleteNode.next; deleteNode.value = nextNode.value; deleteNode.next = nextNode.next; // nextNode의 next 를 deleteNode의 next로 줌으로써 nextNode 를 지운다.   이런 식의 생각의 전환이 코딩 인터뷰에서는 필요한 것 같다.

 

 

 

문제 : 단방향 연결 리스트에서 x 값을 갖는 노드를 기준으로 연결리스트를 나누는 코드를 작성하라. x 보다 작은 값을 갖는 노드들은 x 값보다 크거나 같은 값을 갖는 노드들보다 앞쪽에 와야 한다.   풀이 : 가장 간단하게 푸는 방법은, merge sort 를 반대로 하듯이, 연결 리스트를 읽어가면서 기준보다 작은 값은 A연결리스트에 넣고, 큰 값은 B연결리스트에 넣은 다음 나중에 둘이 합치면 된다.   다른 방법이 있다. 퀵정렬처럼 풀면 되겠다. index 를 두 개 주고, 하나는 "x값보다 큰 값", 하나는 "x값보다 작은 값"을 찾도록 해서 둘의 값을 swap 시키면 된다. 그림으로 풀어보면 아래와 같다. 아래 index에서 l과 r은 첫번째, 두번째 노드에서부터 규칙에 맞게 연결 리스트를 순회한다. l은 3보다 큰 값을, r은 3보다 작거나 같은 값을 찾으면 순회를 멈추고, 둘의 값을 swap 한다. r이 끝에 다달으면 코드는 종료된다.

 

문제 : 주어진 연결 리스트가 회문(팰린드롬)인지 검사하라.   풀이 : 간단하게, 중간까지의 원소들을 stack 에 쌓고, 나머지 원소들과 하나씩 비교해보면 된다. header 에서 a, b 두 개의 포인터를 만든다. a가 한 번 이동할 때 b는 두 번 이동한다. b가 마지막에 다닿았다면 a는 연결리스트의 중간에 있게 된다. a는 이동하면서 stack 에 원소들을 하나씩 push 한다. a가 중간지점에 오면(b가 마지막에 왔을 때) stack 에는 연결리스트의 앞부분의 반이 역순으로 들어가게 된다. a를 중간 지점부터 마지막까지 이동시키면서 stack 에서 하나씩 pop 한 값과 비교해본다. a가 마지막에 도달할 때꺼정 stack 의 pop 값과 틀린 것이 없다면 회문이 된다.