[LeetCode] 24. Swap Nodes in Pairs 페어의 노드 스왑

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

24번 Swap Nodes in Pairs는 입력받은 연결 리스트를 페어단위로 스왑하는 문제이다.

Example

위 문제는 혼자 풀려고 해보았지만, 푸는 도중에 꼬이고 어떤식으로 풀어야할지 전혀 감이 잡히지 않아 책 풀이를 참고하였다.

책 풀이 코드를 이해하며 작성하는 시간을 가졌다. 

 

# 풀이방법 1 - 반복 구조로 스왑 (책 풀이 참고)

# 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를 가리키도록 함 - 과정 1
            b= head.next
            head.next = b.next
            b.next = head
            
            # 이전 노드 prev가 b를 가리키도록 함 - 과정 2
            prev.next = b
            
            # 다음 반복문을 위해 이동 
            head = head.next
            prev = prev.next.next
        
        return root.next

while 반복문을 이용하여 head를 순회한다. 

1.  b가 현재 노드 head를 가리키도록 함 

2. 이전 노드 prev가 b를 가리키도록 함 

3. 다음 반복문을 위해 이동 

 

| 이해과정 |

코드의 과정 1, 2를 그림으로 이해하며 풀어보았다.

 

| 핵심 |

while head and head.next :
            # b가 현재 노드 head를 가리키도록 함 
            b= head.next
            head.next = b.next
            b.next = head

            # 이전 노드 prev가 b를 가리키도록 함 
            prev.next = b
            # 다음 반복문을 위해 이동 
            head = head.next
            prev = prev.next.next

 

 

# 결과 

 

 

연결리스트 너무 어렵다... 다시 볼 필요가 있어보인다.