LeetCode 24( Swap Nodes in Pairs, Python)

1. 문제 링크

• Swap Nodes in Pairs - LeetCode

Swap Nodes in Pairs - LeetCode

2. 문제 설명

• 주어진 연결 리스트의 인접한 두 (홀수, 짝수) 노드를 서로 바꾸어 (짝수, 홀수)로 반환
• 예시1) [1, 2, 3, 4] 주어지면 [2, 1, 4, 3]
• 예시2) [1] 주어지면 [1]
• 예시3) [1, 2, 3, 4, 5] 주어지면 [2, 1, 4, 3, 5]

3. 처음 풀이

• 일단 연결 리스트를 다루는 것이 어색하였는데 생활 코딩의 설명과 생활 코딩에서 이용한 애니메이션으로 시각화한 사이트가 도움되었다.
  • (생활코딩: Linked list - Data Structure (자료구조) (opentutorials.org), 시각화: Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo)
• 스스로 단계별로 그림을 그려보면 그나마 이해가 쉽다.
• 머리가 쪼개어지는 줄 알았다!!!
• 일단 나의 풀이는 별로임. 어쨋든 어떻게 풀었냐하면…
• 1번과 2번의 위치를 바꿀 때는 1번, 2번, 3번의 정보가 필요하다. 총 3개에 집중하면 됨
• 2번과 3번의 위치를 바꿀 때는 1번, 2번, 3번, 4번 총 4개에 집중해야 함.
• 따라서 중간 부분들을 바꿀 때는 인접한 4개를 보며 4개 중 가운데 2개를 바꾸면 됨.
• 그러다가 끝에 가면 3개만 보고 바꾸면 됨 .
• 따라서 첫 부분, 중간 부분, 마지막 부분을 따로 짰음.

# 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]:
        #길이가 0 or 1
        if not head or not head.next:
            return head

        #길이가 2
        print(head)
        if not head.next.next:
            temp = head
            head = temp.next
            head.next = temp
            head.next.next = None
            return head



        #길이가 3이상, 1번↔2번
        cur = head
        temp = cur.next
        cur.next = cur.next.next
        temp.next = cur
        head = temp

        #길이가 3이상, 중간 부분들 서로 바꾸기
        while cur.next and cur.next.next:
            temp2 = cur.next.next.next
            temp1 = cur.next
            cur.next = temp1.next
            cur = cur.next
            cur.next = temp1
            temp1.next = temp2
            cur = cur.next

        #길이가 3이상, 끝 쪽 남은 부분 처리
        try:
            temp2 = cur.next.next.next
            temp1 = cur.next
            cur.next = temp1.next
            cur = cur.next
            cur.next = temp1
            temp1.next = temp2
            cur = cur.next
        except:
            pass

        return head

4. 다른 풀이

• 가장 이해가 잘 된 설명 (🚀SWAPPING NODES (Not just the values) || Visual Explanation || Well Explained || C++ - 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]:
        # 빈 리스트이거나 노드가 하나뿐인 경우 처리
        if not head or not head.next:
            return head

        # 더미 노드를 앞쪽에 추가, cur는 head, prev는 한 칸 앞 Node 가르킴
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        cur = head

	#Node가 딱 떨어지거나 하나 남으면 멈춤
        while cur and cur.next:
            # 교환할 노드들(temp1, temp2 교환)
            temp1 = cur
            temp2 = cur.next

            # 교환 수행 1단계
            temp1.next = temp2.next

			#교환 수행 2단계
            temp2.next = temp1

			#교환 수행 3단계
            prev.next = temp2

            # 다음 쌍으로 이동
            prev = temp1
            cur = temp1.next


        return dummy.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]:
        #길이 0이나 1인 경우
	if not (head and head.next): 
            return head
        def swap(node):
            if node == None:
                return None
		#1번과 2번 바꾸기
            if node.next:
                head = node.next
                tmp = swap(node.next.next) #3번에 재귀
                node.next = tmp
                head.next = node
                return head
            return node
        return swap(head)

5. 배운 점

• 앞쪽은 따로 처리해야 한다고 생각했는데 제일 앞에 dummy를 추가하면 한 번에 가능
• 그리고 마지막 쪽을 따로 처리한 이유가 None.next 하면 에러가 나기 때문인데 마지막 노드에 next를 한 tail.next는 None이지만 에러는 아님. 이를 이용하면 마지막 쪽도 한 번에 할 수 있음.
• 연결 리스트에서도 재귀를 종종 떠올려 주자.