[Leetcode] 206. Reverse Linked List

✅ 문제 - 역순 연결 리스트

 

---

✅ 풀이

💡 Point

이 문제는 연결리스트를 역순으로 연결하는 것이다.
연결리스트란? 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않으며 각 노드마다 포인터를 통해 다음을 참조할 주소를 가진다.
따라서 이 문제의 포인트는 이전 노드의 주소를 참조하게끔 바꾸는 것이다.

 

 

연결리스트 head = [1, 2, 3, 4, 5] 일 때를 생각해보자.

배열처럼 순서가 있어보이지만 사실은 물리적인 순서가 아닌 포인터로 다음에 올 노드를 참조하는 것이다.

연결리스트는 주소를 참조하고 있다는 것만 알고 있으면 포인터를 이전 노드로 참조하도록 바꾸어주면 역순으로 연결이 된다.

기본 연결 리스트

 

바꾸고자 하는 연결 리스트

 

 

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev = head, None
        
        while node: #node의 값이 있을 동안
        	#temp에 현재 노드의 다음 노드값을 담고 현재 노드가 참조하는 주소를 이전 노드로 바꿈
            temp, node.next = node.next, prev
            # 현재 노드는 prev로 보내고 다음 노드를 현재 노드로 당겨줌
            prev, node = node, temp
            
        return prev

 

위 코드를 간단하게 해석해보자면,

 

1. temp = node.next를 통해 임시 변수에다가 다음에 올 노드값을 저장한다.(현재 노드 당겨오기 위한 작업)

2. node.next = prev 를 통해 현재 노드가 참조하는 주소를 이전 노드값으로 한다.(2가 3을 참조하고 있었지만, 2가 1을 참조하도록)

3. prev = node를 통해 참조 주소 변경이 완료된 현재 노드를 이전 노드로 옮김

4. node = temp를 통해 다음 노드를 현재 노드로 옮겨서 다시 while문을 돌며 참조 주소 변환을 한다.