[ch_08]연결리스트

[ 파이썬 알고리즘 인터뷰_알고리즘 스터디 리뷰 ]

---

* 팰린드롬 판별 -> deque 활용

( 리스트 에서 pop(0) 과 pop() 으로 비교할 경우, pop 연산을 할 때마다 값들이 shift 되기 때문에 O(n) 소요 )

- 이중 연결 리스트 구조의 deque 를 사용하면, popleft() 와 pop() 을 비교하는 연산 수행 시 O(1) 소요된다.

from collections import deque
deq = deque()
    
while len(deq)>1:
	if deq.popleft() != deq.pop():
		return False

---

* 연산자 우선순위

- and 연산자가 or 보다 우선순위 높다.

- 슬라이싱 > 배열 >..지수 > 비트연산 not : 우선순위가 꽤 높은 연산자들

- 이런거 헷갈리니까 우선순위가 가장 높은 괄호 표시해주는 게 좋다.

---

* 역순 연결리스트 생성 시, 이동방향 나타내주는 변수 + prev 변수 ( 역순 next 지정 )

node, prev = head, None
while node:
	next_node, node.next = node.next, prev
	prev, node = node, next_node
return prev

---

* 자료형 변환 ( 연결리스트 <-> 파이썬 리스트 )

- 연결리스트 -> 리스트 : 노드들 value 값 리스트에 append

- 리스트 -> 연결리스트 

def toLinkedList(result:List): # 리스트 to 연결리스트
            
    head = ListNode(result[0])
    nextNode = head

    for i in range(1,len(result)):
    	nextNode.next = ListNode(result[i])
        nextNode = nextNode.next

    return head

---

* 숫자 리스트를 단일 값으로 합치기 

: 숫자 하나씩 str 형태로 꺼내서 합친 후, int 로 형 변환

a = [1,2,3,4,5]

#1 
nums = int(''.join(str(num) for num in a))
# nums = <class 'int'>

#2 
nums2 = ''.join(map(str,a))
# nums2 = <class 'str'>

---

* 연결리스트 내 지정된 구간만 뒤집기 

- 지정된 구간 : start 와 end 변수로 구간 판단하기

- 뒤집을 때 사용할 변수 추가로 사용한다.(temp)

def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        
        if head is None or left == right:
            return head
        
        root = ListNode(None)
        root.next = head
        
        start, end = root, root.next
        for _ in range(left-1): # 시자 구간과 end 지정
            start = start.next
        end = start.next
        
        for _ in range(right - left):
            temp = start.next
            start.next = end.next
            end.next = end.next.next
            start.next.next = temp
            
        return root.next