파이썬 알고리즘 인터뷰_8장.연결리스트

연결 리스트는 가장 대표적인 선형 알고리즘.

효율적으로 풀기 위해서 첫번째 방법은 deque를 이용하여 최적화 시킬 수 있다. 동적 배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다. 왜냐하면 첫번째 값을 꺼내오면 모든 값이 한 칸씩 shifting되며, 시간 복잡도도 O(n) 가 발생한다. 파이썬의 deque는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)에서 실행된다. 

두번째 방법은 런너를 이용하는 것이다.  순서에 따라 2개의 런너, 빠른 런너와 느린 런너를 각각 출발 시키면, 빠른 런너가 끝에 다다를 때 느린 런너는 중간 지점에 도달하게 된다. 그럼 느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나간다. 이제 중간에 도달한 느린 런너가 나머지 경로를 이동할 때, 역순으로 만든 연결 리스트의 값 들과 일치 하는지 확인해나가면 된다. 

 

런너 기법

런너는 연결 리스트를 순회할때 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 빠른 러너는 2개, 느린 러너는 1개씩 이동하게 된다. 이때 빠른 런너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간 지점을 가리키게 된다. 이 같은 방식으로 중간 위치를 찾아내면, 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용할 수 있어 연결 리스트 문제에서는 반드시 쓰이는 기법이다.

# 빠른 런너 fast와 느린 러너 slow의 초깃값은 다음과 같이 head에서 시작
slow = fast = head

# next가 존재하지 않을 때 까지 이동

# 빠른 러너인 fast는 두칸 씩, 느린 러너 slow 는 한칸 씩 이동
# 그러면서 역순으로 연결 리스트 rev를 생성하는 로직을 slow 앞에 붙인다.

while fast and fast.next:
	fast = fast.next.next
    rev, rev.next = slow, rev
    slow = slow.next
    
    if fast:
    	slow = slow.next
        
    # 패린드롬 여부
    while rev and rev.val == slow.val:
    	slow, rev = slow.next, rev.next
    return not rev

 

역순 연결 리스트

풀이 1. 재귀 구조로 뒤집기

# 다음 노드 next 와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다.
# node.next 에는 이전 prev 리스트를 계속 연결해 주면서 node가 None이 될 때 까지 재귀 호출하면 마지막에는 
# 백트래킹 되면서 연결 리스트가 거꾸로 연결된다. 

def reverseList(self, head: ListNode) -> ListNode:
  def reverse(node: ListNode, prev: ListNode = None):
      if not node:
          return prev
      next, node.next = node.next, prev
      return reverse(next, node) #재귀
  return reverse(head)

풀이 2. 반복 구조

def reverseList(self, head: ListNode) -> ListNode:
	node, prev = head, None
    
    while node:
    	next, node.next = node.next, prev
        prev, node = node, next
    
    return prev
    
# 재귀보다 반복이 더 공간 복잡도도 낮고, 런타임 시간도 더 빠르다.

 

역순 연결 리스트 2

풀이 1. 반복 구조로 노드 뒤집기

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

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

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