Leetcode 143. Reorder List

파이썬에서 링크드 리스트 형을 인자로 전달해서 메서드 호출하기 

headData = ListNode(1, 
	        ListNode(2, 
	            ListNode(3, 
	                ListNode(4, 
	                    ListNode(5, None)))))
	
# reorderList 호출
solution = Solution()
solution.reorderList(headData)

 

디버깅

 

내가 처음에 풀때는 18째줄을 생각해내지 못했었는데, 18번째 줄을 빼먹고 run했을때 Memory Limit Exceeded 가 나온다는 것이었다. 도저히 왜 Memory Limit 초과가 나오는지도 이해하기 어려웠어서 디버깅 해본 내용을 포스팅한다.

 

이슈

 

head를 slow.next = None 으로 끊어주지 않으면 

결국 `head` 는 1->2->3->4->None 값을 가지고 

뒷부분을 뒤집고 난 `secondNext` 는 5->4->None 값을 가지게 때문에 

첫 부분과 뒷 부분을 하나씩 가져와서 차례로 머지할때 1 - 5 - 2 - 4 - 3 - 4- 3 - 4- 3 - 4 - ......

이렇게 무한 루프에 빠지게되어 리트코드에서 돌릴때 Memory Limit Exceeded 가 발생하게 된다.

 

 

위 그림과 같이 첫부분의 3.next 는 4가 되고, 4.next 는 3이 되기 때문에 첫 부분과 두번째 부분을 머지하는 코드의 31번째 while 문에서 무한 루프에 빠지게 된다. 

 

 

해결

이렇기에 head를 앞부분까지 자르기위해서 slow.next = None 처리를 해주어야한다. 

즉, 두번째 second half 를 만든 이후에 바로 첫번째 half가 가리키고 있는 마지막 노드를 None 으로 가리켜서 first half와 second half 를 나눈다.

 

slow.next = None 처리를 하고 난 이후에 second half 를 뒤집어주는 코드를 25번째 줄까지 실행하고 나면 위 캡처처럼 첫번째부분의 마지막 노드.next도 None 으로 끝나고, 두번째 부분의 마지막노드.next도 None 으로 끝남을 볼 수있다.

이제 이 두 부분의 노드를 하나씩 merge하면 second 가 None이 될때까지 잘 머지됨을 확인할 수 있다.