Python 알고리즘 인터뷰 - 문제15. 역순 연결 리스트

leetcode 206. Reverse Linked List - https://leetcode.com/problems/reverse-linked-list/description/

 

예제1

입력

1->2->3->4->5->NULL

 

출력

5->4->3->2->1->NULL

 

풀이

재귀함수를 사용한 풀이

재귀함수를 통해 코드를 구현하면 다음과 같다.

def reverse(node, prev = None):
	if not node:
    	return prev
     
    next, node.next = node.next = prev
    return reverse(next, node)

 

1->2->3->NULL 리스트를 기준으로 reverse함수 호출 진행을 살펴보면 다음과 같다.

먼저 call1에 대해서 설명해본다. reverse 함수를 처음 호출할 때는 node는 첫번째 head 값으로, prev는 None으로 호출한다.

next, node.next = node.next, prev 구문을 통해 node는 None을 가리키고 next는 다음 리스트로 이동한다.

def reverse(node, prev = None):
	...   
    next, node.next = node.next = prev

이후 reverse(next, node)를 호출하여 call2, call3을 진행한다. 위와 마찬가지로 현재 node는 prev를 가리키고 next는 node의 다음 값으로 이동하는 것을 반복한다.

call4에서는 node == None이다. 이 경우 prev(=3)를 반환한다. 여기서 prev는 역순 리스트에 새로운 head의 위치이다. 

def reverse(node, prev = None):
	if not node:
    	return prev

이후 call3->call1 까지 순차적으로 prev(=3)을 return하여 함수를 종료한다. 

 

전체 코드는 다음과 같다.

def reverseList(self, head):
    def reverse(node, prev = None):
        if not node:
            return prev

        next, node.next = node.next, prev
        return reverse(next, node)

    return reverse(head)

반복문을 사용한 풀이

재귀함수를 사용하지 않더라도 다음과 같이 반복문을 사용하여 위치를 뒤집을 수 있다. 다음과 같이 node.next를 prev 연결 및 next 위치를 이동 한 후 prev = node, node = next 진행을 반복한다.

 

node가 None에 위치하면 다음과 같이 역순으로 연결된 리스트를 구할 수 있다. 

전체 코드는 다음과 같다.

def reverseList(head):
	node, prev = head, None
    while node:
    	node.next, next = prev, node.next
        prev, node = node, next
        
    return prev