[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 7장 연결리스트

- 리스트는 순서가 있는 값들의 모음(collection)

- 노드는 하나의 객체와 다음 노드에 대한 참조로 이루어짐

- 이중 연결리스트는 이전 노드에 대한 참조도 가지고 있다.

- 삽입 및 삭제는 지역적 발생하므로 시간복잡도 O(1)

- 검색은 모든리스트 순회해야 하므로 O(n)

 

class List<T> {
	public T data; // 나
	public ListNode<T> next; // 다음
}

---

7.1 두 개의 정렬된 리스트 합치기

단순 연결리스트 L과 F에 숫자가 오름차순 저장되어 있다.
L과 F를 합쳐 하나의 단순 연결리스트 반환하기 (단, 오름차순 유지)

힌트 : 정렬된 배열은 인덱스 두개로 합칠 수 있다.

리스트는 반복자가 끝에 도달했을 때 처리에 주의할 것

- 두 개의 리스트를 앞에서부터 확인하면서 작은 키를 가지고 있는 노드를 선택해 나가는 방법

 

7.2 부분 리스트 하나 뒤집기

리스트의 부분 리스트를 역순으로 재배열하기
(헤드노드부터 1번, 노드 추가해선 안됨)

힌트 : 갱신해야 할 다음 노드를 주의깊게 보자

- 직접적으로는 부분리스트를 뽑아서 뒤집고 이어붙이기

- 부분리스트 시작부분을 마주치면 뒤집고 마지막 부분을 마주치면 멈추는 방법(시간복잡도 O(n)) 

 

7.3 사이클이 존재하는지 확인하기

단순 연결리스트의 헤드가 주어졌을 때, 사이클이 존재하면 사이클의 시작노드를, 그렇지 않으면 null 반환하기
(단, 리스트의 길이를 사전에 알 수 없음)

힌트 : 두 개의 반복자를 사용해서 하나는 빠르게, 하나는 느리게 움직여 보자

=> 천천히는 노드를 한개씩, 빠르게는 두 개씩 방문한다. 어느 순간 같은 노드 가리킨다면 사이클이 존재함

(빠르게 움직이는 반복자가 느리게 움직이는 반복자를 건너뛴다면, 그 다음 단계에 두 반복자는 만나게 되어 있기 때문)

- 공간 제약 없다면 방문했던 노드들을 해시테이블에 넣고 현재 노드가 이전에 방문했던 노드인지 확인(공간복잡도 O(n) 추가)

- 이중루프로 재방문했는지 확인하기(시간복잡도 O(n^2))

 

7.4 사이클이 없는 두 리스트가 겹치는지 확인하기

두 개의 단순 연결리스트가 동일한 노드 리스트를 공유할 수도 있음(플라이웨이트패턴 통해 메모리 절약 또는 정규형태 유지 목적)

사이클 없는 단순 연결리스트 두 개가 주어졌을 때, 두 리스트가 노드를 공유하는지 판단하라

힌트 : 단순한 경우 먼저 생각

- 무식하게 하나의 리스트에 있는 노드를 모두 해시 테이블에 넣고 해당 노드가 존재하는지 확인해 보기(시간, 공간복잡도 O(n))

- 이중루트로 두번째리스트가 첫번째 리스트에 있는지 확인해보기(시간복잡도 O(n))

- 서로 겹치는 리스트는 테일을 공유해야 한다(공유하고 있는 테일을 찾아라)

=> 두 리스트의 길이 확인 후, 짧은 것은 헤드에서 시작 & 긴 것은 두개의 차이 만큼 앞에서 시작해서 같이 한 칸씩 나아간다.

그러면 처음으로 공유하는 노드에서 만나게 됨(만약 끝까지 공유노드 찾지 못하면 없다는 뜻)

 

7.5 사이클이 존재하는 두 리스트가 겹치는지 확인하기

공유하는 노드가 존재한다면 어떻게 찾아야 할까?

해시테이블 사용 또는 케이스 분석하여 공간 복잡도 개선하기

1) 하나는 사이클 존재 / 다른 하나는 사이클 존재하지 않음 => 공유하는 노드 없음

2) 두 리스트 모두 사이클 존재 => 두 리스트가 겹친다면 반드시 동일

=> 사이클이 시작되기 전에 만나는 경우는 둘이 만나는 첫 번째 노드가 단 하나여야 함 7.4사용

=> 사이클이 시작된 후 만나는 경우는 7.3사용

 

7.6 단순 연결리스트에서 노드 삭제하기

단순 연결리스트의 노드 삭제하기

주어진 노드 삭제하려면 이전 노드의 next 필드를 갱신해야 한다.

하지만 삭제할 노드가 마지막이 아니고 값을 쉽게 복사할 수 있다면 O(1) 시간에 삭제 가능

- 다음 노드의  값을 복사 후 다음 노드 삭제하면 현재 노드 삭제한 듯한 효과

 

7.7 리스트에서 뒤에서 k번째 원소 삭제하기

단순 연결리스트와 정수 k가 주어졌을 때 리스트의 끝에서 k번째 원소를 삭제하기
(단, 리스트의 길이와 상관없이 메모리는 상수 크기 만큼만 추가로 사용 가능)

힌트 : 리스트의 전체 길이 모른다면 쉽지 않다. 만약 알수 있다면 반복자 두개로 끝에서 k번째 찾을 수 있을까?

- 무식하게 먼저 단일 패스로 길이 구한 후, 다시 리스트 반복하면서 삭제할 노드 찾는 방법 (시간복잡도 O(n^2))

- 반복자 두 개로 리스트 순회하는 방법 (시간복잡도 O(n), 공간복잡도 O(1))

=> 첫 번째 반복자는 두 번째 반복자보다 k만큼 앞서게 배치한 후 함께 앞으로 나아간다.

첫 번째 반복자가 리스트의 마지막에 왔을 때 두 번째 반복자는 끝에서 k + 1 번째 노드를 가리키게 되므로, 끝에서 k번째 삭제 가능

 

7.8 정렬된 리스트에서 중복된 원소 삭제하기

정수가 정렬된 단순 연결리스트에서 중복되는 부분을 제거하기

힌트 : 갱신해야 할 next 필드에 주목

- 무식하게 해시테이블로 중복 제거 후 새로운 리스트 만드는 방법 (공간복잡도 O(n))

- 새로운 리스트를 매번 탐색하면서 추가하려는 값이 이미 존재하는지 확인하는 방법 (공간복잡도 O(n), 시간복잡도 O(n^2))

- 리스트 순회하며 인접한 노드 값이 동일한 경우, 현재 노드를 삭제하는 방법 (공간복잡도 O(1), 시간복잡도 O(n))

 

7.9 단순 연결리스트에서 오른쪽 원형 시프트 구현하기

자연수 k와 단순 연결리스트가 주어졌을 때, 오른쪽으로 원형 시프트를 k번 수행한 뒤의 리스트를 반환하라

힌트 : 배열을 회전하는 문제와 다른 점이 무엇인지 생각해보자

- 무식하게 오른쪽 시프트 연산을 k번 수행하는 방법(공간복잡도 O(1), 시간복잡도 O(kn), k가 n보다 클 수도 있다.)

- 마지막 노드 t를 찾고 t의 다음 노드는 기존의 헤드가 되어야 하므로 t의 다음 노드를 헤드로 갱신한다.

시프트 연산을 적용한 후 기존 헤드는 k번째 노드가 되어야 하므로 n-k번째 노드를 헤드로 설정한 뒤 환형고리를 끊어준다.

(공간복잡도 O(1), 시간복잡도 O(n))

 

7.10 짝수 - 홀수 병합 구현하기

 숫자가 0부터 차례대로 단순 연결리스트에 쓰여있다.
단순 연결리스트의 연결 순서를 짝수 노드 다음에 홀수 노드가 등장하도록 배치하라

- 무식하게 짝수와 홀수로 이루어진 리스트 두 개를 새로 할당 후, 마지막에 두 리스트 연결하는 방법(시간 및 공간복잡도 O(n))
- 두 개의 반복자 사용

=> 하나는 짝수노드, 하나는 홀수 노드 반복하며 짝수원소는 짝수리스트, 홀수 원소는 홀수 리스트에 연결한 후 마지막에 홀수리스트를 짝수리스트에 연결 (공간복잡도 O(1), 시간복잡도 O(n))

 

7.11 단순 연결리스트가 회문인지 확인하기

시퀀스가 단순 연결리스트로 이루어져 있으면 회문확인이 어려워짐
단순 연결리스트가 주어졌을 때 이 리스트가 회문인지 확인하는 방법

힌트 : 리스트를 앞뒤로 동시에 읽기

- 처음 노드와 마지막 노드 비교 후, 두 번째 노드와 뒤에서 두 번째 노드를 비교하는 작업 반복하는 방법(공간복잡도 O(1), 시간복잡도 O(n^2))

- 리스트의 절반을 역순으로 뒤집어 비교 (공간복잡도 O(1), 시간복잡도 O(n))

 

7.12 리스트의 피벗 구현하기

피버팅(pivoting) : 어떤 정수 k를 기준으로 k 보다 키가 작은 노드는 왼쪽에, 큰 노드는 오른쪽에 배치하는 과정

단순 연결리스트와 정수 k가 주어졌을 때, k를 기준으로 리스트를 피버팅하기
단, k이전에 나온 노드들과 이후에 나온 노드들의 상대적인 순서는 변하지 않아야 함

힌트 : 세 개의 영역을 독립적으로 형성한다.

- 무식하게 세 개의 리스트 생성 후 입력리스트를 순회하며 노드의 키값이 k 보다 작은지, 같은지, 큰지에 따라 서로 다른 리스트에 넣기

그 후 입력리스트를 헤드부터 순회하며 세 개의 리스트에 있는 자료 덮어쓰기 (시간 및 공간복잡도 O(n))

- 기존 리스트를 순회하면서 각 노드를 세개의 리스트로 재 배치하는 방법(공간복잡도 O(1), 시간복잡도 O(n))

 

7.13 리스트로 표현된 정수의 덧셈

(제한이 없는 정수 표현할 때 종종 쓰인다)

각 노드에 쓰인 단순 연결리스트를 하나의 정수로 생각하여 (뒤에서부터 읽음) 덧셈 수행하기

예) 

L1 -> 3 -> 1 -> 4 (413)

L2 -> 7 -> 0 -> 9 (907)

// L -> 0 -> 2 -> 2 -> 1 (413 + 907 = 1320)

힌트 : 각 쌍의 숫자를 합이 9를 넘는 경우가 없다고 가정하고 풀 것

- 덧셈 방식 사용하여 두 리스트에서 각 자릿수를 차례로 더해준다.

마지막 올림수가 0이 아닌 경우에는 새로운 노드 하나 추가 (시간복잡도 O(n + m), 공간복잡도 O(max(n , m)))