[파이썬 알고리즘] 역순 연결 리스트2

역순 연결 리스트2

리트코드로 풀러 가기

인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

입력
1 -> 2 -> 3 -> 4 -> 5 -> NULL, m = 2, n = 4

출력
1 -> 4 -> 3 -> 2 -> 5 -> NULL

처음 생각한 방법은 뒤집을 연결 리스트의 앞, 뒤의 노드를 저장해둔 뒤 스왑을 시작하면서 연결해주는 방식이었지만, 필요이상의 연산과 코드의 복잡성이 문제가 되어 책의 풀이를 설명한다.

반복 구조로 노드 뒤집기

스왑을 시작할 인덱스의 바로 전 노드가 스왑하고 난 후의 연결 리스트의 시작점이 되고, (start 노드)

스왑을 시작할 인덱스가 스왑된 부분 연결 리스트의 종점이 된다. (end 노드)

스왑을 진행한 후, 스왑된 첫 부분 (이전의 start 노드의 next 노드)가 붕 떠버리므로, 미리 start.next 노드를 temp로 저장해 둔 뒤, 스왑후 연결해준다.

위의 아이디어에서 출발하여 start와 end 노드를 고정시킨 후 스왑해줄 수 있다.

설명이 다소 복잡하고 직관적이지 못하지만, 불변하는 시작점과 종점을 저장해둔 뒤, 스왑하는 방식을 기억해두면 응용할 수 있을것 같다.

def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
    if n == m:
        return head
    
    root = start = ListNode(None)
    root.next = head
    for _ in range(m - 1):
        start = start.next
    end = start.next
    
    for _ in range(n - m):
        temp = start.next
        start.next = end.next
        end.next = end.next.next
        start.next.next = temp
    
    return root.next