[leetcode] 206. Reverse Linked List 파이썬 코드

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

 

연결리스트를 reverse 하는 문제이다.

 

단일 연결 리스트 (singly-linked list)

단일 연결리스트에서 각 노드는 '값 (val)'과 '다음 노드에 대한 참조 (next)'를 가지고 있다.

 

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

---

iterative 하게  푸는 방법과 recursive 하게 푸는 방법이 있다.

 

Iterative 하게  푸는 방법

iterative 하게  푸는 방법은 two pointers를 쓰면 된다.

이 방법의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.

class Solution(object):
    def reverseList(self, head):
        prev, curr = None, head

        while curr: # while curr is not Null
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

 

(1) curr의 next를 일단 저장해놔야 한다.

(2) curr.next를 prev로 지정 (reverse)

(3) prev는 curr이 되고

(4) curr는 nxt로 설정해서

while문을 반복하면 연결리스트를 reverse 시킬 수 있다.

 

 

 

Recursive 하게 푸는 방법

class Solution(object):
    def reverseList(self, head):
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None
        return newHead

 

 

참고

https://www.youtube.com/watch?v=G0_I-ZF0S38