[LeetCode 19] Reverse Linked List II

 

Think

역순 연결 리스트 2번째 문제.

전에 봤던 206. 역순 연결 리스트도 완벽히 이해하지 못한 상황이라

206번을 설명해주는 영상을 찾아 보고 왔다.

이해가 훨씬 잘 됐다! 반복과 재귀 두 방법 모두.. 그림이 역시 짱이다

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

 

206번 풀이했던 내용을 바탕으로 

이번 문제는 스스로 풀어보자

반복이 재귀방법보다 공간복잡도도 더 낮고 시간도 짧다.

반복으로 풀어보자

.

.

.

절반밖에 못풀었다^^! 영상을 찾아봤다!

같은 채널에서 올린 영상이 있었고 이해가 역시 잘 됨...

https://www.youtube.com/watch?v=RF_M9tX4Eag 

 

이 문제에서는 주어진 연결리스트의 맨 앞 head노드를 가리키는 root노드를 맨 앞에 하나 더 만들어 활용한다.

 

[이유] 여기서 우리가 유의해야 할 점은 만약 뒤집어야 하는 구간이 맨 처음부터라면?

 

1. 반복문을 돌며 작업을 하게 될텐데,

맨 처음부터 뒤집어야할 경우와 그렇지 않은 경우 한 부분이 달라진다.

중간부터라면 뒤집기 시작하는 노드의 직전 노드가 가리켜야 하는 노드가 달라지므로 이 작업이 필요해진다.

하지만 맨 처음부터라면 뒤집어야 하는 구간 앞의 노드가 없기 때문에 이 작업이 필요없어질 뿐만 아니라

하면 None이므로 에러가 난다. 즉 None인지 아닌지 체크 후 작업해야 한다.

이 때 root 노드도 리스트에 원래 포함되어있는 노드처럼 취급해 작업한다면?

root가 항상 있으니 None일 일이 없으므로 걱정을 할 필요가 없다.

 

2. 이 문제에서는 마지막에 결과 리스트의 맨 앞 노드를 답으로 반환해야 한다.

맨 앞 노드가 변경되어 버리고 기존에 주어진 head는 더이상 head가 아니게 된다.

하지만 root 노드도 리스트에 원래 포함되어있는 노드처럼 취급해 작업한다면?

root 노드는 항상 현재의 head노드를 가리키되고,

root가 가리키는 노드를 답으로 반환하도록 한다면 해당 케이스에 대비할 수 있다.

 

혼자 풀기를 시도했을 때에도 이 문제를 해결하지 못해서 Submit을 성공하지 못했다.

알면 알수록...마술같을 뿐

영상 보고 있으면 걍 예술이란 말밖에 안나옴

영상 속 설명 그림

그 후에는 뒤집어야 할 구간을 뒤집는다.

이 부분은 206번과 같다.

한 가지 가져갈 점은 반복문을 몇 번 돌아야 할 지 생각할 때

작업을 하나로 생각하지 말고 None을 가리키는 작업을 하더라도 노드(형체가 분명한 대상)를 하나로 생각하는 게 

생각하기 쉽다는 점이었다.

항상 작업을 하나로 생각해 버릇해서 반복문에서 많이 헷갈렸는데(항상 print찍어서 확인함)

이런식으로도 생각하려 해야겠다.

 

 

Solution

# 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 reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """

        root = ListNode(None, head) #None값을 갖고 head를 가리키는 노드 생성
        
        prev, cur = root, head
        
        #뒤집기 시작하는 노드까지 cur을 이동
        for _ in range(left-1) :
            prev, cur = cur, cur.next
        
        before, start = prev, cur #뒤집기 직전 노드 갖고있기, 뒤집기 시작 노드 갖고있기
        prev = None
        
        #뒤집기 진행
        for _ in range(right-left+1) :
            next, cur.next = cur.next, prev #킵하고 끊으면서 이전거 가리키기
            prev, cur = cur, next #포인터 이동
            
        #뒤집기 후 앞뒤 노드 연결
        before.next = prev
        start.next = cur
        
        return root.next

 

** 혼자 짰던 코드

# 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 reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        node = head
        prev = None
        
        
        for i in range(left-1) :
            prev, node = node, node.next
        
        before = prev
        
        start = node
        
        prev, node = node, node.next
        
        for _ in range(left, right) :    
            next, node.next = node.next, prev
            node, prev = next, node
        
        start.next = node
        before.next = prev
        
        return head

 

 

Get

• idea : 주어진 연결리스트의 맨 앞 head노드를 가리키는 root노드를 맨 앞에 하나 더 만들어 활용
• idea : 한 가지 가져갈 점은 반복문을 몇 번 돌아야 할 지 생각할 때
  작업을 하나로 생각하지 말고 None을 가리키는 작업을 하더라도 노드(형체가 분명한 대상)를 하나로 생각하는 게 
  생각하기 쉽다는 점이었다.
  항상 작업을 하나로 생각해 버릇해서 반복문에서 많이 헷갈렸는데(항상 print찍어서 확인함)
  이런식으로도 생각하려 해야겠다.