12/19일 알고리즘 스터디

jswboseok·2022년 12월 14일

Leetcode 24. Swap Nodes in Pairs

리스트가 주어졌을 때 앞 - 뒤 노드 pair에서 값을 바꾸는 문제입니다.

Input : 리스트의 head
Output : pair 단위로 swap된 리스트

풀이 1

현재 노드를 가리키는 cur 변수를 설정합니다. cur의 초기값은 head가 됩니다.
cur.val → cur.next.val로 바꾸고 cur.next.val → cur.val로 바꾸어줍니다.
현재 cur의 다음다음 노드로 이동합니다 (cur = cur.next.next)

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        
        while cur and cur.next:
            cur.val, cur.next.val = cur.next.val, cur.val # swap
            cur = cur.next.next # 다음다음 노드
        
        return head

풀이 2

root = prev인 빈 노드 하나를 생성합니다.
prev가 head를 가리키도록 합니다.
head의 다음 노드를 b로 놓은 후 head.next를 b.next로, b.next를 head로 놓습니다.
prev가 b를 가리키도록 합니다.
head = head.next와 prev = prev.next.next로 이동합니다.
이를 반복하다보면 연결된 노드들이 서로 바뀌게 됩니다. 최종적으로 마지막 그림과 같이 됩니다.

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[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

Leetcode 328. Odd Even Linked List

리스트가 주어졌을때 홀수 번째 노드들이 먼저 오고 짝수 번째 노드들이 나중에 오도록 리스트를 구성합니다. 이 때, 홀수 번째 노드들이나 짝수 번째 노드들 안에서의 순서는 주어진 리스트의 순서를 따르도록 합니다.

※ 착각한 것은 홀수 인덱스의 노드와 짝수 인덱스의 노드를 나누는 것이지 홀수값이 있는 노드와 짝수값이 있는 노드를 나누는 것이 아니다.

풀이

첫 번째 노드를 odd, 두 번째 노드를 even으로 놓습니다.
odd와 even의 next는 다음다음 노드를 가리키도록 합니다. (odd.next → odd.next.next / even.next → even.next.next)
odd와 even을 다음으로 이동시킵니다.
마지막노드에 도달하면 완료되면 (마지막 노드를 제외하고) odd는 odd만 노드끼리만 연결되고 even은 even 노드끼리만 연결됩니다.
마지막 odd 노드의 next로 첫 번째 even 노드를 가리키게 합니다.

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root = odd = head
        even_root = even = odd.next
        while odd.next:
            odd.next = odd.next.next
            even.next = even.next.next
            odd = odd.next
            even = even.next
        
        odd.next = even_root # 마지막 odd 노드에 even의 root를 이어준다
        return root

Leetcode 92. Reverse Linked List II

리스트와 두 가지 인덱스 left와 right가 주어집니다. left번째 노드와 right번째 노드 사이의 노드들을 reverse 시킵니다.

Input : 리스트의 head, 왼쪽 인덱스 number, 오른쪽 인덱스 number
Output : left와 right 사이가 전반된 리스트

풀이 1

left번째 노드로 먼저 갑니다.
for문을 (right - left)번만큼 돌려서 right를 찾도록 합니다.
각각 val을 바꾸어줍니다.
left, right를 각각 1씩 증가, 감소시키고 left의 다음 노드로 갑니다.
중간을 찾기 전까지 반복합니다. (left < right)

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        root = left_node = head
        i = 1
        while i < left: # left번째 node를 찾음
            left_node = left_node.next
            i += 1
        
        while left < right:
            right_node = left_node
            for i in range(right - left): # right번째 node를 찾음
                right_node = right_node.next
            temp = left_node.val # swap
            left_node.val = right_node.val
            right_node.val = temp
            left += 1
            right -= 1
            left_node = left_node.next

        return root

풀이 2

책에 있는 풀이입니다. 책에는 어떤 link를 제거해야 하는지 나와있지 않아 그림으로 다시 그려보았습니다.

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        root = start = ListNode(None)
        root.next = head
        
        for _ in range(left-1):
        	start = start.next
        end = start.next
        
        for _ in range(right-left):
        	tmp, start.next, end.next = start.next, end.next, end.next.next
        	start.next.next = tmp
        return root.next