[leetcode] 206번 Reverse Linked List

206번 역순 연결 리스트

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

Reverse Linked List - LeetCode

 

풀이 1 - 배열에 저장하여 뒤집기

class Solution:
    def reverseList( head: Optional[ListNode]) -> Optional[ListNode]:
        arr = []
        while head :
            arr.append(head.val)
            head = head.next
    
        tmp = None
        head = None
        
        arr = arr[::-1]
        
        for val in arr:
            if not tmp:
                tmp = ListNode(val)
                head = tmp #첫번째 주소 저장
            else:
                tmp.next = ListNode(val)
                tmp = tmp.next

        return head

아직 파이썬에 linked list 개념이 어색해서 리스트에 저장해서 뒤집고 다시 연결리스트에 넣어주었다. 

연결 리스트 개념을 이용해서 푼건 아니지만 속도는 해당 풀이가 좀 더 빠르긴했다.

 

풀이 2 - 연결 리스트를 유지한 상태에서 역순으로 주소 변경해주기

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

        while node :
            next = node.next #node의 다음 주소 임시 저장해두기
            node.next = prev #head 기준 반대로 주소 저장하기

            prev = node #하나씩 뒤로 head이동
            node = next #다음 노드로 이동
            
        return prev

연결 리스트를 역순으로 뒤집는 문제는 매우 일반적이며, 활용도가 높아서 외워두는게 좋을 것 같다. 

대입이 헷갈리지만 node.next 변수가 다음 node 주소를 저장한 현재 노드라는 걸 잘 인식하면 이해하는데는 크게 어렵지않다. 

 

 

 

 

열코🔥