[LeetCode]Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/

Swap Nodes in Pairs - LeetCode

 

문제 분석

서로 인접해있는 노드를 뒤집는 문제입니다. 단, 값을 바꾸는 것이 아니라 링크의 연결을 바꾸어야 합니다.

 

처음 시도한 답안

# 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]:
        a = head
        dummy = b = ListNode()
        count = 0
        # a : 홀수번째의 노드를 기억하고 짝수번째 카운트에서 바꿔치기하는 역할
        # b : 바꿔치는 노드들을 기록하기 위한 용도
        while head:
            count += 1
            # 짝수의 카운트인 경우
            if count % 2 == 0:
                # 현재 등장한 노드를 연결하고
                b.next = ListNode(val=head.val)
                b = b.next
                # 홀수 카운트에서 저장했던 a노드를 연결시킵니다.
                b.next = ListNode(val=a.val)
                b = b.next
            # 홀수 카운트인 경우, a에 그 노드의 값을 기억해둡니다.
            else:
                a = head
                # head 노드가 홀수개이고, 마지막 노드라면 b에 등장한 노드를 연결시킵니다.
                if not head.next:
                    b.next = ListNode(val=head.val)
            head = head.next

        return dummy.next

접근 방법

1. head 노드가 끝날때까지 순회합니다.
2. 홀수번째 반복의 경우 등장한 노드를 a에 저장합니다.
3. 짝수번째 반복의 경우 등장한 노드를 b에 연결하고 2번에서 저장해둔 a노드를 연결시킵니다.
4. 만약 head 노드의 개수가 홀수개이고, 마지막 노드가 된다면 맨 뒤에 등장한 노드를 연결시킵니다.
5. dummy의 다음 노드를 통해 b 노드에서 기록한 것들을 return 합니다.

처음 딱 문제를 마주했을 때 떠올랐던 풀이방법입니다. 홀수번째의 반복에는 해당 노드를 기록해두고 짝수번째 연결에서 연결된 상태들을 서로 바꿔주면 되지 않을까 했습니다. 다만, 정답은 맞출수 있었지만 ListNode를 계속 초기화하고 불필요한 조건들도 생긴 것 같아 다른 솔루션도 참고해보았습니다.

 

두번째로 시도한 답안 

# 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]:
        dummy = ListNode(0, head)
        prev, curr = dummy, head

        while curr and curr.next:
            # save ptrs
            nxt_pair = curr.next.next
            second = curr.next

            # reverse this pair, 숫자쌍을 뒤집고 노드 재연결
            second.next = curr
            curr.next = nxt_pair
            prev.next = second

            # update ptrs, 바꾼 순서를 기준으로 한칸씩 전진
            prev = curr
            curr = nxt_pair

        return dummy.next

접근 방법

1. curr와 curr의 next 노드가 존재할때까지 반복합니다.
2. nxt_pair는 현재 노드의 2번째 뒤에 있는 노드입니다.
3. second는 현재 노드의 바로 뒤에 있는 노드 입니다.
4. second노드의 다음을 nxt_pair가 아닌 현재 노드로 연결합니다.
5. 현재 노드의 다음을 second가 아닌 nxt_pair로 연결합니다.
6. prev노드의 다음을 second 노드로 연결합니다.
7. 바꾼 순서를 기준으로 현재 노드와, prev노드를 전진합니다.

말로만 풀어쓰면 설명이 어렵기에 아래의 그림을 참고합니다.

1. (Dummy, prev) -> (1, curr) -> (2, second) -> (3, next_pair) -> 4
2. (Dummy, prev) -> (1, curr) -> (2, second) -> (1, curr) -연결 끊어짐- (3, next_pair) -> 4
   2의 next를 1로 연결합니다. 3과의 연결은 끊어진 상태입니다.
3. (Dummy, prev) -> (1, curr) -> (2, second) -> (1, curr) -> (3, next_pair) -> 4
   1의 next를 3으로 연결합니다. 1은 두번 연결된 상태입니다.
4. (Dummy, prev) -> (2, second) -> (1, curr) -> (3, next_pair) -> 4
   prev의 next를 2로 연결해 두번 연결된 1을 끊어줍니다.
5. (Dummy) -> (2, second) -> (1, prev) -> (3, curr) -> 4 
   swap이 완료되었습니다.
6. 이 과정을 반복합니다.