TIL_220515_연결 리스트 알고리즘

원래 어제 올릴 생각이었지만 어제는 Python 문법 관련 내용을 따로 준비하느라 시간이 부족했음
내용을 좀더 추가하고 오늘 올림

[팰린드롬 연결 리스트]

https://leetcode.com/problems/palindrome-linked-list/
연결 리스트가 팰린드롬 구조인지 판별하라

# 내 답안의 구조가 답지의 답안과 유사해 답지로 대체
# 답안1: 리스트 변환
def isPalindromeList(head):
    arr = []

    if not head: # 빠른 반환을 위한 예외처리
        return True

    node = head	
    while node:	# 연결리스트 내용을 전부 arr라는 list에 넣어줌
        arr.append(node.val)
        node = node.next

	# 리스트의 처음과 끝 요소를 하나씩 꺼내서 비교함
    while len(arr) > 1:
        if arr.pop(0) != arr.pop():
        	# 요소가 다른 경우 팰린드롬이 아니기 때문에 False를 반환
            return False

    return True

# 답안2: 데크를 활용
'''
차이점은 자료형이 list에서 deque를 사용하고, 가장 처음 요소를 popleft로 가져옴
기존 list는 인덱스 0에서 하나 뽑아오면 기존 요소의 인덱스를 다 당겨줘야 해서 시간 복잡도 O(n)가 발생함
데크(Deque)는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)이 발생함
'''
def isPalindromeDeque(head):
    q: Deque = collections.deque()

    if not head:
        return True

    node = head
    while node is not None:
        q.append(node.val)
        node = node.next

    while len(q) > 1:
        if q.popleft() != q.pop():
            return False

    return True

# 답안3: 러너를 활용
'''
fast는 한번에 2번, slow는 한번에 1번을 이동함
반복은 fast가 전부 돌때까지
즉 fast가 끝에 도달하면 그 절반을 이동한 slow는 리스트에 중앙에 위치함
slow가 이동하는 동안, rev라는 리스트는 다음 순서에 현재 값을 담고, 현재 값에 slow에 값을 담음
즉 slow가 동하는 동안 rev는 이동한 경로를 역순으로 리스트로 삼음

초기에 fast를 반복할 떄, 다음값이 존재하는지 체크함
홀수를 구분하기 위해서이며, 2번씩 이동하다가 1개만 남은 경우 반복하지 않음
그 홀수에 대해서는 바로 아래에 if fast:로 값이 아직 존재하면
slow.next로 slow를 다음 단계로 보내버리는 것으로 해결
혼자 남은 하나뿐인 워드는 팰린드롬 검사가 필요하지 않음

검사 단위에서는 slow는 리스트의 절반에 도달했고, rev는 slow가 지나온 길을 역순으로 가지고 있음
중앙을 중심으로 기존에 요소들(rev) 남은 요소들(slow)를 한단계씩 비교를 진행함
rev의 요소가 존재하고, rev와 slow의 값이 일치하는 경우
rev와 slow를 다음 단계로 이동
만약 일치하지 않으면 rev는 요소를 아직 보유한 채로 return 코드에 도달
return not rev는 rev에 요소가 없으면 false를 반환하는데, 이떄 not은 true와 false를 뒤바꿈,
즉 요소가 없으면 팰린드롬 검사가 잘 진행이 됬고, 반환 된 false를 true로 바꿔서 return

일단 fast, slow 방식은 리스트 중간을 구할 때 유용해보임
또한 역순으로 리스트를 보관하는 방식도 참고해둬야 겠음 
'''
def isPalindromeRunner(head):
    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.val:
        slow, rev = slow.next, rev.next
    return not rev

[두 정렬 리스트의 병합]

https://leetcode.com/problems/merge-two-sorted-lists/
정렬되어 있는 두 연결 리스트를 합쳐라.

# 내 답안
'''
while로 list1과 list2에 다음 값이 있나 검증.
있으면 하나씩 꺼내서 넣고 남은건 그냥 붙이는 형식
'''
def mergeTwoListsMyway(self, list1: ListNode, list2: ListNode) -> ListNode:
	result = ListNode() 
    # result에 연결 리스트를 생성하고 복사한 result_List를 연산에 사용
    # 리스트를 병합 한뒤에 처음 지점을 반환해야 하기 때문에 result를 남겨둠
    result_List = result
    # 두 리스트 모두 값이 존재하면 계속 반복을 함
    while list1 and list2:
    	# 두 리스트의 값 중 작은 것을 result_list에 다음 요소로 넣고
    	# 해당 list는 다음 요소로 넘어감 
    if list1.val < list2.val:
    	result_List.next = list1
    	list1 = list1.next
    else:
    	result_List.next = list2
    	list2 = list2.next
    	result_List = result_List.next
    
    # list1, list2간 길이가 다르면 루틴이 끝나도 한개의 리스트는 요소를 추가로 더 가지고 있음
    # 남은 값이 있는지 확인하고, 존재하는 경우 result_list.next에 담음
    # 남아있는 전체 요소를 전부 result_list에 연결시켜 주는 것임
    if list1:
    	result_List.next = list1

	elif list2:
    	result_List.next = list2

	# 이후 처음 요소를 가지고 있는 result를 반환해 지금까지 연결시킨 모든 요소를 반환
    return result.next
        
# 답안: 재귀 구조로 연결
'''
[입력값]
1->2->4(list1)
1->3->4(list2)

[루틴 분석] 
list1이 존재하지 않는 경우 True
or list2가 존재하고 list2의 값이 작은 경우 True
조건을 만족하면 list1과 list2의 값을 뒤바꿈

이후 list1 내용이 존재할 경우 재귀함수를 실행해 list1에 다음 값으로 넣어줌

초기에 list1을 존재하지 않는지 확인하는 이유는
재귀 함수 호출 시 list1.next 값을 list에 담아줌
즉 지속적으로 next로 이동하다 보면, 다음 값이 없는데 list1에 넣은채로 함수를 호출하게 됨
이때 마지막 처리를 위해 list1이 없는 경우 list2에 있는걸 그대로 가져옴(형식적으로는 서로 뒤바꾸면서)
마지막 처리 후에도 list1 다음 값이 없고, list2와 뒤바꿔도 list1에 아무것도 없으면
반환을 시작함

반환을 시작한 순간 마지막에 반환 되는건 첫번째 실행할 때 초기 list1 요소임
재귀함수가 반복 되는 동안 list1에 요소들이 서로 연결되었기에 처음 요소만 반환해도 전부 참조 가능

[입력값 기반 상세 루틴]
이동은 list 1만 함 계속 이동하면서 작은거 나오면 뒤바꾸고 반복임    
list 1: 1->2->4(첫 포지션 도착, 1이랑 1 비교해서 뭐 없으니 다음 순서로 넘어감)
list 2: 1->3->4

list 1: 1->2->4(2 순서에 도착, 비교해보니 List 2에 있음)
list 2: 1->3->4(애네를 통째로 list 1에 2->4와 바꿈)

list 1: 1->1->3->4(바꾸고 3 포지션 도착)
list 2: 2->4(list2에 작은게 있음)

list 1: 1->1->2->4(또 바꿈, 참고로 이 4는 list2에 2랑 붙어있던 4임 list1에 달린 4가 아니라)
list 2: 3->4(list1은 뒤바꾸고 다시 다음 단계로 갔음 근데 다음 단계가 4라서 또 털릴 예정)

list 1: 1->1->2->3->4(또 뒤바꿈 list2는 가진거 다 털리고 큰거 짬처리용 됨)
list 2: 4

list 1: 1->1->2->3->4->4(비교할꺼 하고 넘어갔는데 다음게 없음, 놀라서 list2에 있는거 털어옴)
list 2: 아무것도 없음(꼭... 그렇게...다 가져가야만 속이 시원했냐!)

처음에 if (not list1) 없을 경우 true
이거 왜 있나 했더니 다 털어먹고 내가 가진게 안남으면 list2 털어올려고 만든거였음

하나씩 작은거 나올떄마다 그냥 남에 떡이 커보인다고 통째로 바꾸면서 야금야금 먹다가 남은거 하나마저 털어먹고
if list1:
때려서 안에 데이터 없으니깐 재귀함수 그만 호출함
return 할때는 list2 마지막 남은 요소까지 쪽쪽 털어먹고 난 이후임

return 나온 순간 지금까지 재귀함수 했던거 만큼 계속 return하면서 털어온 전리품 단계별로 하나씩 반환함    
아무리 봐도 악독한 코드임

'''
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        if (not list1) or (list2 and list1.val > list2.val):
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1

[역순 연결 리스트]

https://leetcode.com/problems/reverse-linked-list/
연결 리스트를 뒤집어라

# 내 답안
'''
palindrome_linked_list에서 사용했던 러너 방식에 착안해서 그대로 돌려봄
의외로 쉽게 됨
'''
def reverseListMyway(self, head: ListNode) -> ListNode:
    result = None
    while head:
        result, result.next, head = head, result, head.next
    return result
    
# 답안 1 재귀함수
'''

일단 처음에 head 하나 들고 시작함
처음에 reverse 들어올땐 prev 값이 없으니 None 기본값이 들어감

node라는 이름으로 들어가서 내용이 없는지 확인함(마지막에 반환용)
재귀 들어가면 처음에 반환 코드 고려를 해야겠음(경우에 따라서)
일단 값이 있으니 들어가서 node에 다음 값을 next라는 변수에 넣어줌
이전 값은 node에 다음 값으로 넣어주는데, 처음엔 이전 값이 없으니 생략

일단 node에 다음 값과 현재 값을 각각 node와 prev에 넣고 반복함
반복을 계속 하면 결국 다음값이 계속 마지막으로 가고 현재 값은 prev에 계속 교체됨
마지막에 다음 값이 없다고 할땐 계속 끌고 왔던 현재 값을 반환해줌
끝까지 갈때까지 끌고온 현재값은 기존 node에 마지막 값임
현재 재귀가 종료되면서 기존 node에 마지막 값을 가져오면
이전 재귀도 종료 되면서 

head = 5->4->3->2->1

1차 루틴
node = 5->4->3->2->1
next = 4->3->2->1(node.next 값을 가져오면서 다른 요소들도 연결됨)
node = 5->None(node.next에 prev 값(처음엔 Neno)을 넣으면서 현재 값 5에 next 값들이 사라짐)

2
node = 4->3->2->1(이전 루틴에 next 값을 가져옴)
prev = 5(이전 루틴에 node 값을 가져옴 ->None 내용은 그냥 사라졌다는거 알려주는 거니깐 이제 안적음)
next = 3->2->1(다시 node.next 값을 넣어줌)
node = 4->5(node.next에 prev 값(5)을 넣음, 앞으로 단계가 계속 될 때마다 node에 다음 요소를 하나씩 가져옴)

...반복중...

node = None(하나씩 가져오다가 결국 바닥남)
prev = 1->2->3->4->5(애가 다 쳐먹었음)

이제 if not node 검사를 실시함
node가 비었으니깐, prev를 반환해줌
return이 시작됬으니 아래에 next, node.next 같은건 신경 안써도됨
'''
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)
    
# 답안 3 반복 구조로 뒤집기
'''
node = 5->4->3->2->1
    prev = None
    
    next = node.next: 4->3->2->1(node의 다음 단계인 4 부터 넣어줌)
    node.next = prev: 5->None (node 다음 단계에 prev 부여해줬지만 현재 prev는 내용이 없음, 앞으로 None은 안적을꺼임)
    prev = node: 5-> (아까 자기가 node.next를 None으로 조져놓고 자기가 node를 먹음)
    node = next: 4->3->2->1(Node는 또 next를 먹음 아주 지들끼리 돌리고 난리났음)
    
    next = node.next: 3->2->1 (node.next를 넣었는데, node는 이전 루틴에서 next를 먹었음. 즉 여기서 .next는 하나씩 먹겠다는 의미)
    node.next = prev: 4->5 (prev의 내용을 node에 다음에 이어붙임)
    prev = node: 4->5   (자기가 붙인 내용을 그대로 보존)
    node = next: 3->2->1
    정리하면 next는 node의 앞길을 따로 보관함
    prev는 node 앞길 막으면서 한개만 남기고 잘라낸 다음 자기껄 붙이고 그걸 가져옴
    node는 한대 얻어터지고 나면 next가 돌아와서 보관하고 있던거 돌려줌(근데 기존거 없이 다음꺼부터 줌)
    
    next = node.next
    node.next = prev
    prev = node
    node = next
    구조를 반복하면서 prev가 한개씩 먹다가 반복문 다 돌아서 node에 남은게 없으면 return하는 형식
'''
def reverseListRepeat(self, head: ListNode) -> ListNode:
    node, prev = head, None

    while node:
        next, node.next = node.next, prev
        prev, node = node, next
    return prev

[홀짝 연결 리스트]

https://leetcode.com/problems/odd-even-linked-list/
연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라

# 자료를 계속 조사하다가 점점 답안과 내 답이 비슷해졌기에 큰 차이가 없어서 답안을 올림
'''
반복을 할 대상을 even으로 잡고 even.next로 다음요소 까지 검증함
변수를 이어 붙여서 쓰긴 했지만 떼서 써도 상관없음
obb와 even은 별개로 동작함
각자 자신의 다음 요소를 다다음 요소로 넣고(서로 짝수 홀수 피하려고)
다음 주소로 이동함
즉
obb: 1->2(건너뜀)->3->4->5
even: 2->3(건너뜀)->4->5
다음 요소를 건너뛰고 현재 요소에 다다음 요소를 연결
obb: 3->4->5
even: 4->5
현재 요소를 다음으로 연결
이때 2->4, 1->3 형태로 연결되면서 2개의 리스트로 분리됨 각 리스트의 첫 요소(시작점, 인덱스)는 각각
head: 1->3->4->5
index: 2->4->5
가 보유하고 있으며, head는 return용 index는 head에 합치기 용으로 선언된 것임
처리는 obb와 even이 진행
반복문 돌고 나면 어차피 짝수를 기준으로 돌린거니 짝수가 남지 않음
홀수가 남든 말든 어차피 마지막은 홀수임
안남으면 그냥 붙여버리면 되고,
남았으면 남은거 리스트에 붙어 있을테니 거기 붙여버리면 됨

obb.next로 홀수의 마지막에 짝수 시작 요소 보관해둔거(index)붙여주고
처음 요소를 그대로 간직한 head를 반환해주면 끝
'''
def oddEvenList(self, head: ListNode) -> ListNode:
    # 예외처리
    if head is None:
        return None

    obb = head
    even = head.next
    even_head = head.next

    # 반복하면서 홀짝 노드 처리
    while even and even.next:
        obb.next, even.next = obb.next.next, even.next.next
        obb, even = obb.next, even.next
    obb.next = even_head
    return head

[느낀점]

연결 리스트를 제대로 다루지 못하면서 삽질을 많이 했음
초반까지 모르고 삽질 했던 가장 큰 이유는
연결 리스트를 다른 변수에 넣어주면 그건 리스트 자체를 복제하는게 아님
리스트에 수많은 요소중 하나를 복사하는 것이고,
그 요소는 다음 요소의 정보를 가지고 있음
즉, 변수는 달라도 해당 변수가 가진 다음 요소의 정보로 연결이 되어 있다는 것

예를들어 홀짝 문제에 경우
head: 1->2->3->4->5
even: 2->3->4->5
이렇게 있는데 even = None 하고 head를 조회하면 아무런 일도 없음 어차피 복사된 정보이기 때문
다만 even.next = None 으로 다음 요소를 찾아 들어가고 None을 적용시키면 Even에 다음 요소인 3번 정보가 사라지면서
head 조회시 1->2로 조회됨 3번정보가 소실되고, 4번을 찾아 갈 수 없기 때문

당연한건데 이걸 이해를 못해서 시간을 많이 버림