[Book Review] Python Algorithm Interview (5)

[Book Review] Python Algorithm Interview (5) : 연결 리스

1. 연결 리스트

연결리스트

• 기본 선형자료구조 중 하나
• 다양한 추상 자료형 (ADT) 구현의 기반이 됨
• 동적으로 새로운 노드를 삽입하거나 삭제하기 간편
• 연결구조를 통해 물리메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉬움
• 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용 가능
• 물리메모리에는 구조체 각각이 서로 연결된 형태로 구성되어있으며 메모리 어딘가에 여기저기 흩뿌려진 형상을 띤다
• 배열과는 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야하므로 상수시간에 접근할 수 없다. = 탐색시간 O(n) 반면 시작 또는 끝지점에 아이템을 추가하거나 삭제,추출하는 작업은 O(1)에 가능

답안에 포함

class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

ㅤ
ㅤ

ㅤ
ㅤ

Q13. 팰린드롬 연결리스트

Q. 연결리스트가 팰린드롬 구조인지 판별하라

입력

1->2->2->1

출력

true

1) 리스트 변환
파이썬의 리스트는 pop()함수에 인덱스 지정 가능해서 마지막 요소 아니라도 원하는 위치 자유롭게 추출가능

def isPalindrome(self, head: ListNode) -> bool:
  q: List[]
ㅤ
  if not head:
    return True
    node = head
ㅤㅤㅤ
  while node is not None:
    q.append(node.val)
    node = node.next
ㅤ
  while len(q) > 1:
    if a q.pop(0) != q.pop():
      return False
ㅤ
  return True

2) 데크를 이용한 최적화
앞선 풀이의 문제점 : pop(0)에서 첫번째 아이템을 추출할때의 속도문제
동적배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다.

(첫번째값을 꺼내오면 모든 값이 한칸씩 시프팅(shifting)되며 시간복잡도 O(n)이 발생하기 때문, 최적화를 위해서는 맨 앞에 데이터를 가져올 때 O(n)이내에 처리할 수 있는 자료형 필요

파이썬 데크(Deque)는 이중연결리스트 구조로 양쪽방향 모두 추출하는데 시간복잡도는 O(1)
-> 양방향 모두 O(1)에 가능한 데크를 설명
(두군데만 수정하면 됨)

q : List = [] 대신에 q: Deque = collections.deque()
ㅤ
if q.pop(0) != q.pop(): 대신에 if q.popleft() != q.pop():

3) 런너를 이용

• fast / slow 두가지 리스트 구성
• slow를 역순 리스트로 둬서(rev)

def isPalindrome(self, head: ListNode) -> bool:
  rev = None
  slow = fast = head
ㅤ
  while fast and fast.next:
    fast = fast.next.next
    rev, rev.next, slow = slow, rev, slow.next
  if fast:
    slow = slow.next
ㅤㅤ
  while rev and rev.val == slow.va:
    slow, rev = slow.next, rev.next
  return not rev

런너기법

• 연결리스트 순회할 때 2개의 포인터를 두는 방식/ 한 포인터가 다른 포인터보다 앞서게하여 병합 지점이나 중간위치 길이 등을 판별할 떄 유용하게 사용
• 보통 빠른 런너는 두 칸씩 건너뛰고 느린 런너는 한칸씩 이동 / 빠른 런너가 연결 리스트의 끝에 도달하면 느린 런너는 정확히 연결 리스트의 중간지점을 가리키게됨.
• 이런식으로 중간위치 찾아내면 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용가능

다중 할당
파이썬에서 다중 할당 (multiple assignment) 2개 이상의 값을 2개 이상의 변수에 동시에 할당하는 것
a,b = 1,2
이처럼 한 번에 여러 개의 값을 여러 변수에 할당할 수 있음

rev, rev.next, slow = slow, rev, slow.next

와

rev = slow
rev.next = rev
slow = slow.next

는 다름

(동일한 참조와 상이한 참조)
전자의 경우 한번의 트랜잭션으로 끝나게됨.

파이썬의 경우 원시타입이 없고 모두 객체이다
(문자와 숫자의 경우)
할당을 진행할 때 값을 할당하는 것이 아니라 불변 객체에 대한 참조를 할당
숫자 5와 변수 a=5 b=5 모두 동일한 ID
(메모리 상에는 단 하나만 존재, ab 두 변수는 각각 이 값을 가리키는 참조)
-> 불변객체이기 때문에 5라는 숫자를 변경한다고 해도 a,b 두 변수의 id가 6으로 변하지 않음
but 숫자가 아닌 리스트와 같은 자료형일 경우 내부의 값은 변할 수 있음. 이 경우 리스트를 참조하는 모든 변수의 값도 따라 바뀜

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q14. 두 정렬 리스트의 병합

Q. 정렬되어있는 두 연결리스트 합치기

입력

1->2->4, 1->3->4

출력

1->1->2->3->4->

1) 재귀구조로 연결

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  if (not l1) or (l2 and l1.val > l2.val):
    l1, l2 = l2, l1
  if l1:
    l1.next = self.mergeTwoLists(l1.next, l2)
  return l1

변수 스왑 = 다중 할당

기본 방식

temp = a
a = b
b = temp

파이썬

a : int = 1
b : int = 2
a,b = b,a

숫자형식 스왑

x += y
y = x – y
x -= y

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q15. 역순 연결리스트

연결 리스트를 뒤집어라

입력

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

출력

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

1) 재귀 구조로 뒤집기

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

반복이 재귀에 비해 70%수준의 메모리 차지해 공간복잡도 낮고 실행 속도 약간 빠름 (둘다 큰문제 없음)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q16. 두 수의 덧셈

Q. 역순으로 저장된 연결리스트의 숫자를 더하라

입력

(2 -> 4 -> 3) + (5 -> 6 -> 4)

출력

7 -> 0 -> 8

1) 자료형 변환

# 연결리스트 뒤집기
def reverseList(self, head: ListNode) -> ListNode:
  node, prev = head, None
ㅤㅤ
  while node:
    next, node.next  = node.next, prev
    prev, node = node, next
  return prev
ㅤ
# 연결리스트를 파이썬 리스트로 변환
def toList(self, node: ListNode) -> List:
  list: List = []
  while node:
    list.append(node.val)
    node = node.next
  return list
ㅤㅤ
# 파이썬 리스트를 연결 리스트로 변환
def toReversedLinkedList(self, result: str) -> ListNode:
  prev: ListNode = None
  for r in result:
    node = ListNode(r)
    node.next = prev
    prev = node
  return node
ㅤㅤ
# 두 연결 리스트의 덧셈
def addTwoNumber(self, L1: ListNode, l2: ListNode) -> ListNode:
  a = self.toList(self.reverseList(l1))
  b = self.toList(self,reverseList(l2))
  resultStr = int(‘ ’.join(str(e) for e in a)) + int(‘ ’.join(str(e) for e in b))
ㅤ
#최종 계산 결과 연결리스트 변환
return self.toReversedLinkedList(str(resultStr))

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q17. 페어의 노드 스왑

Q. 연결리스트를 입력받아 페어단위로 스왑

입력

1->2->3->4

출력

2->1->4->3

1) 값만 교환

def sapPairs(self, head: ListNode) -> ListNode:
  cur = head
ㅤ
  while cur and cur.next:
    #값만 교환
    cur.val, cur.next.val = cur.next.val, cur.val
    cur = cur.next.next
  return head

-> 좋지 않은 피드백 받을수도

2) 반복 구조로 스왑

def swapPairs(self, head: ListNode) -> ListNode:
  root = prev = ListNode(None)
  prev.next = head
  while head and head.next: 
    b = head.next
    head.next = b.next
    b.next = head
ㅤ
    prev.next = b
 ㅤ
    head = head.next
    prev = prev.next.next
  return root.next

3) 재귀 구조로 스왑

def swapPairs(self, head: ListNode) -> ListNode:
  if head and head.next:
    p = head.next
    haed.next = self.swapPairs(p.next)
    p.next = head
    return p
  return head

공간복잡도 낮음

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q18. 홀짝 연결리스트

Q. 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성

공간 복잡도 O(1), 시간복잡도 O(n)

입력

2->1->3->5->6->4->7->Null

출력

2->3->6->7->1->5->4->Null

1) 반복구조로 홀짝 노드 처리

def oddEvenList(self, head: ListNode) -> ListNode:
  if head is None:
    return None
ㅤ
  odd = head
  even = head.next
  even_head = head.next
ㅤ
  while even and even.next:
    odd.next, even.next = odd.next.next, even.next.next
    odd,even = odd.next, even.next
ㅤ
  odd.next = even_head
  return head

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q19. 역순 연결리스트 2

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

입력

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

출력

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

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