[코딩인터뷰] 연결리스트 - 역순 연결리스트 문제풀이

문제

연결리스트를 뒤집어라.

 

입력 : [1 -> 2- > 3 -> 4 -> 5 -> NULL]
출력 : [5 -> 4 -> 3 -> 2 - > 1 -> NULL]

 

 

 

 

정답코드

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return

출처 : github.com/onlybooks/algorithm-interview/blob/master/3-linear-data-structures/ch08

 

 

 

 

 

문제풀이

문제를 보면 단순하지만 쉽지 않은 문제였다. 우선 역순으로 연결리스트를 연결하기 위해 현재 node와 node.next (노드가 가르키는 노드)를 올바르게 swap 해야한다.

 

while node:
    next, node.next = node.next, prev
    prev, node = node, next

 

1) next 변수에 현재 node가 가르키는 다음 노드를 저장한다.

2) 현재 node가 가르키는 다음 노드를 prev로 변경한다.

3) prev 변수에 현재 노드를 저장한다.

4) node 변수에 next (현재 node가 가르키는 다음 노드)를 저장한다.

 

 

[과정]

1) node = 1

next = 2

node.next = None

 

prev = 1  (다음 노드 차례의 반복문 실행시, 다음 노드가 가르킬 노드)

node = 2 (다음 차례의 노드 설정)

 

2) node = 2

next = 3

node.next = 1 (=prev)

 

prev = 2 (다음 노드 차례의 반복문 실행시, 다음 노드가 가르킬 노드)

node = 3

 

3) node = 3

next = 4

node.next = 2

 

prev = 3 (다음 노드 차례의 반복문 실행시, 다음 노드가 가르킬 노드)

node = 4

 

4) node = 4

next = 5

node.next = 3

 

prev = 4 (다음 노드 차례의 반복문 실행시, 다음 노드가 가르킬 노드)

node = 5

 

5) node = 5

next = NULL

node.next = 4

 

prev = 5 

node = NULL

 

결과적으로 node를 출력하게되면 5 -> 4 -> 3 -> 2 -> 1 임을 알 수 있다.