Leetcode Python - 24. Swap Nodes in Pairs

Leetcode #24 - Swap Nodes in Pairs

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 24 ‘Swap Nodes in Pairs’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 dummy listNode를 만드는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        dummy = prev = cur = ListNode(0)
        dummy.next = head
        cur = cur.next
        
        while cur.next:
            prev.next = cur.next
            cur.next = cur.next.next
            prev.next.next = cur
            
            if not cur.next:
                break
            prev = prev.next.next
            cur = cur.next
        return dummy.next

시간복잡도는 O(n) : 길이 n의 linked list를 n/2번 순회함

공간복잡도는 O(1) : dummy LisNode를 생성