[리트코드(LeetCode)] 92. Reverse Linked List II - Python

leetcode.com/problems/reverse-linked-list-ii/submissions/

Reverse Linked List II - LeetCode

 

 

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

 

풀이

연결리스트는 순서에 대한 값을 가지고 있지 않아서 인덱스를 통한 탐색은 불가하다. 때문에 앞에서부터 m번째 노드, n번째 노드를 찾아내야 한다.

이 문제에서는 m ~ n번째 노드들에 한해서만 순서를 거꾸로 뒤집는다. revers linked list I의 문제처럼 뒤집는 원리는 같지만 뒤집힌 구간의 연결리스트를 m-1번째 노드, n+1번째 노드와 앞,뒤로 잘 이어줘야한다.

 

m-1번째 노드를 start에 저장하고,

m번째 노드를 end에 저장한다. (m번째 노드는 결국 뒤집힌 구간 마지막에 가기 때문)

 

start와 end의 노드가 지정이 되면 n - m만큼 for문을 돌면서 해당 구간에 있는 노드를 뒤집는다.

tmp라는 변수에는 start.next를 저장하고, start.next에는 end.next, end.next에는 end.next.next를 저장한다. 그리고 start.next.next에 tmp를 다시 저장한다.

1 - 2 - 3 - 4 - 5 라는 연결리스트에서 2~4까지 뒤집어야한다면

start => 1

end = > 2가 되고,

tmp => start.next인 2

start.next = > end.next인 3

end.next => end.next.next인 4

start.next.next => tmp인 2

 

이를 다시 연결시켜보면

1(start) - 3(start.next=end.next) - 2(start.next.next=tmp, end) - 4(end.next) - 5 가 된다.

 

이러한 반복 구조로 코드를 작성하면 원하는 결과가 나온다.

class Solution:
    # 내 풀이
    # 시작 부분, 뒤집어지는 부분, 끝 부분으로 나누고 뒤집어지는 부분을 연산한 뒤 시작, 끝 부분과 연결 함
    def reverseBetween_mySolution(self, head: ListNode, m: int, n: int) -> ListNode:
        root = start = ListNode()
        root.next = head

        for i in range(m - 1):
            start = start.next

        end = start.next

        node, prev = start.next, None
        for i in range(n - m + 1):
            next, node.next = node.next, prev
            node, prev = next, node

        start.next = prev
        end.next = node

        return root.next

    # 책 풀이
    # 반복문으로 뒤집어지는 부분을 연산하면서 시작, 끝 부분을 계속해서 이어주는 방법
    # 직관적으로 받아들이기 쉽지 않았다.
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head or m == n:
            return head

        root = start = ListNode()
        root.next = head

        # start, end 지정
        for _ in range(m - 1):
            start = start.next
        end = start.next

        # 반복하면서 노드 차례대로 뒤집기
        for _ in range(n - m):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp

        return root.next

www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178

파이썬 알고리즘 인터뷰 - 교보문고