[LeetCode] 24. Swap Nodes in Pairs

문제 링크 : leetcode.com/problems/swap-nodes-in-pairs/

Swap Nodes in Pairs - LeetCode

이 문제는 linked list의 노드를 두 개씩 짝을 지어 swap한 후 head를 반환하는 문제이다.

 

풀이방법

swap은 짝수번째 마다 일어난다.

swap 후에는 홀수번째가 되므로 다음 노드로 이동한다.

head, mid, tail로 노드의 조건을 나뉘어서 swap하였다.

# 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: ListNode) -> ListNode:
        curr = prev = head
        while curr and curr.next:
            prec = curr.next
            # head
            if curr == head:
                head = curr.next
                curr.next = head.next
                head.next = curr
            # tail
            elif not curr.next.next:
                prev.next = prec
                curr.next = prec.next
                prec.next = curr
            # mid
            else:
                prev.next = curr.next
                curr.next = prec.next
                prec.next = curr
            prev = curr
            curr = curr.next
        return head

다른 풀이를 보니 head 앞에 root 노드를 만들어서 모든 노드에서 동일한 방식으로 swap이 가능하게 푼 방법도 있었다.

알고리즘 문제를 많이 풀어보질 않아서 이런 알고리즘 테크닉들을 익혀두면 알고리즘 문제들을 조금 더 general하게 풀 수 있을 것 같다.

 

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        root = prev = ListNode()
        prev.next = head
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            
            prev.next = b
            
            prev = head
            head = head.next
            
        return root.next