leetcode 206. Reverse Linked List

 

만약에 stack을 쓰게 된다면 O(2n)의 시간복잡도와 시간복잡도가 생기기 마련이다. 

하지만 우리는 포인터 개념으로 여기에 접근하면 O(n)으로도 풀이가 가능하다

 

바로 이전에 저장했던 이전 node들을 저장해서 포인터의 방향을 반대로 바꾸는 것이다

 

코드를 한번 따라가보자

 

 

현재 노드를 뜻하는 curr가 2에 있다고 가정하자.

그렇다면 이전 노드를 뜻하는 prev는 1일 것이고, 3은 curr.next 가 될 것이다.

 

그렇다면 아래의 코드가 이해가 될 것이다

 

curr.next = prev

현재 curr 노드의 next는 prev 노드로 정한다 라는 뜻이다.

 

그럼 prev를 이제 현재 노드로 입력을 해두어야 다음 loop를 쓸 것이다

prev = curr

위와 같이 쓸 수 있다. 자 이제 2의 다음 node로 넘어가야한다.

curr = curr.next #????

그렇다면 curr를 다음 node로 바꾸어야지...

어라 조금 이상하다 순서를 바꾸려고 하기에는 이미 curr.next는 prev로 할당이 되지 않았나?

우리는 그래서 임시로 curr.next를 저장할 변수가 필요하다. 그냥 tmp라 하겠다.

 

tmp = curr.next
curr.next = prev
prev = curr
curr = tmp

기본적인 로직이 완성되었다. 

 

이를 이제 loop를 돌려보자.

while curr:
    tmp = curr.next
    curr.next = prev
    prev = curr
    curr = tmp

 

최종완성 솔루션은 아래이다.

 

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

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        curr = head
        prev = None

        while curr :
            tmp = curr.next
            curr.next = prev

            prev = curr
            curr = tmp

        return prev        



a, b, c, d = ListNode(1), ListNode(2), ListNode(3), ListNode(4)

a.next = b
b.next = c
c.next = d 

s = Solution()
node = s.reverseList(a)

while node :
    print(node.val)
    node = node.next