[파이썬 알고리즘] 8장 - 역순 연결 리스트 (leetcode 206)

https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

 

<문제>

Reverse a singly linked list.

 

<예제>

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

 

---

 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# my solution
def reverseList(head: ListNode) -> ListNode:
    reversed_head = ListNode()
    while head:
        head_next = reversed_head.next              # head 다음 노드 (A) 임시 저장
        reversed_head.next = ListNode(head.val)     # 추가할 노드 (B) 생성하여 head의 다음 노드로 설정
        reversed_head.next.next = head_next         # B 노드 다음 A 노드가 오도록 연결
        head = head.next                            # 입력된 linked list의 next node
    return reversed_head.next                       # 첫 node는 dummy node

 

가장 앞 부분에 새로운 node를 만들어서 연결하기만 하면 된다.위의 코드에서는 코드 작성의 편리함을 위해 dummy node를 추가하였고, 따라서 reversed_head.next를 리턴하게 된다.