Blind 75 | Reorder List (Linked List 4 / 6)

 

연결리스트 뒷부분에서 시작되는 노드들을 앞에서부터 번갈아가며 연결하는 문제로 

 

노드의 val을 임의로 수정하면 안 되고 어떠한 리턴도 하지 않는 함수를 작성해야 한다.

 

뒷부분에서 거꾸로 연결해 야하기 때문에 reverse linked list를 풀 수 있어야 이 문제를 풀 수 있다.

 

 

알고리즘

 

1. slow fast 포인터를 이용하여 노드의 중간 지점을 찾는다.

2. 중간 지점의 다음 노드부터 시작하여 연결 리스트를 거꾸로 연결한다.

3. 두 연결 리스트를 교차하며 연결한다.

 

 

구현

 

 

 

중간 지점을 찾는 첫번째 부분에서는 종이에 그림을 적어 그려 구현하면 더 쉽다.

 

 

두 번째 반을 거꾸로 만드는 작업에서 제일 중요한 부분은 

 

두 번째 반 연결 리스트가 시작되기 직전의 노드의 next를 null로 만들어 한 개의 연결리스트를 두 개로 분할해야 한다.

 

 

마지막으로 두 개의 연결 리스트를 합치는 과정에서는 원래의 연결리스트가 짝수 일 때는 상관 없으나 홀수 일때 

 

second의 개수가 first의 개수보다 1 작기에 second가 null인지 아닌지를 체크하며 연결해 준다.