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

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

인덱스 m에서 n까지를 역순으로 만들기

 

책에서 구현된 코드

def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
    if not head or m == n:
        return head
        
    root = start = ListNode(0)
    root.next = head
    
    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

 

기억해야할 기법

• 링크드 리스트의 포인터 기법 (예제코드)
  
  • start (바뀌지 않음)
    - reverse 구간 직전 노드를 가리킴
  • end (바뀌지 않음)
    - reverse 이전에 reverse 구간의 첫 위치
    - reverse 도중에는 reverse된 구간의 마지막 위치
    - reverse 후에는 reverse 구간의 마지막 위치
    - end.next = end.next.next로 end는 유지하되 next를 바꾸어 다음 index로 인도
  • tmp
    - 옮겨다니며 포인터를 수정
    1) end와 start의 next가 전진
    2) tmp에 start의 next를 저장 (reverse중인 배열의 head)
  • reverse될 배열의 start와 end가 정해진 상태에서, tmp가 옮겨다니며 순서를 뒤집음
• reverse를 위한 reverse 리스트의 head, rear, 그리고 reverse가 끝난 후 head에 연결할 위치(start) 저장

 

내가 구현한 코드

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    left = left-1
    arr = []
    root = head
    res = res_root = ListNode(0)
    while root:
        arr.append(root.val)
        root = root.next

    arr = arr[:left] + arr[left:right][::-1] + arr[right:]

    for i in arr:
        res.next = ListNode(i)
        res = res.next

    return res_root.next

• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘

• 리스트 슬라이싱이라도 + 연산이 들어가서 오래걸릴 줄 알았는데, 생각보다 오래걸리지 않음
• 그러나 연결 리스트에서 포인터를 바꾸는 다양한 기법들을 활용하려면 기억해야할 듯