๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜

[leetcode] 206๋ฒˆ Reverse Linked List

by young-ji 2022. 5. 7.
206๋ฒˆ ์—ญ์ˆœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ

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

 

Reverse Linked List - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

ํ’€์ด 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 ์ฃผ์†Œ๋ฅผ ์ €์žฅํ•œ ํ˜„์žฌ ๋…ธ๋“œ๋ผ๋Š” ๊ฑธ ์ž˜ ์ธ์‹ํ•˜๋ฉด ์ดํ•ดํ•˜๋Š”๋ฐ๋Š” ํฌ๊ฒŒ ์–ด๋ ต์ง€์•Š๋‹ค. 

 

 

 

 

์—ด์ฝ”๐Ÿ”ฅ

 

 

๋Œ“๊ธ€