Reverse Linked List

문제

 

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

우선 구조를 파악하고 코딩해보자.

head의 구조는 어떻게 생겼을까?

펼치기

head : ListNode{val:1, next:ListNode{val:2, next: None}}

 

그럼 head는 어떻게 선언을 했을까? 이해를 위해 역으로 생각보자.

펼치기

head = ListNode(1)

head.next = ListNode(2)

head.next.next = ListNode(3)

 

풀이

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

#     self.val = val

#     self.next = next

class Solution:

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

 

# 1. 복제대상 : head를 그대로 쓰는 것 보다는 새로운 LinkedList Node를 만들자

# 2. 신규헤드 : 빈노드로 구성하자

 

 

# 3. 복제대상을 반복하자

# 4. 다음번 복제할 임시저장 및 인덱스 역할을 할 노드를 만들자

 

# 핵심은 포인터를 역으로 가리키게 하는 것

 

 

class Solution:

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

 

current = head

prev = None #None은 빈 객체를 뜻한다.

 

while current is not None:

    next_node = current.next

    current.next = prev

    prev = current

    current = next_node #다음 대상으로 이동

 

return prev