프로그래밍/[ Python ]

[연결 리스트] 역순 연결 리스트

망나 2021. 1. 25. 20:21

* leetcode 206. Reverse Linked List

 

Q. 연결 리스트를 뒤집어라.

# 입력
1->2->3->4->5->Null

# 출력
5->4->3->2->1->Null

풀이 1. 반복 구조로 뒤집기

def reverseList(head: ListNode) -> ListNode:
    node, prev = head, None
    
    # node.next를 이전 prev 리스트로 계속 연결하면 뒤집어진 연결 리스트를 얻을 수 있다.
    while node:
        next, node.next = node.next, prev
        prev, node = node, next
        
    return prev
    
###
초기화
node = 1->2->3->4->5->None
prev = None

while [1]
next = 2(->3->4->5->None)
node = 1 -> None
prev = 1 -> None
node = 2(->3->4->5->None)

while [2]
next = 3(->4->5->None)
node = 2->1->None
prev = 2->1->None
node = 3(->4->5->None)

while [3]
next = 4(->5->None)
node = 3->2->1->None
prev = 3->2->1->None
node = 4(->5->None)

while [4]
next = 5(->None)
node = 4->3->2->1->None
prev = 4->3->2->1->None
node = 5(->None)

while [5]
next = None
node = 5->4->3->2->1->None
prev = 5->4->3->2->1->None
node = None
###