[python3] 24. Swap Nodes in Pairs

풀이 일자: 23.05.16

난이도: [Medium]

분류: [Linked List]

문제 내용

문제의 내용은 주어진 LinkedList를 홀수번 째 있는 노드와 짝수번 째 노드의 앞뒤를 바뀌는 문제이다.

 

문제 해결 흐름

1. 단순히 LinkedList의 자료구조 문제이기 때문에 그냥 풀면 된다.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node = head;
        i = 1;
        pprev = None;
        prev = None;
        h = None;

        if node == None or node.next == None:
            return node;

        while node:
            if i & 1: 
                prev = node;
                node = node.next;
            else:
                if h==None: h = node;
                tmp = node.next;
                node.next = prev;
                prev.next = tmp;
                if pprev: pprev.next = node;
                pprev = prev;
                node = tmp; 

            i += 1;
        
        return h;

 

Time Complexity:  O(N)

Node 전체의 순회가 이루어질 수 밖에 없기 때문에 N의 시간복잡도를 가진다.

 

Space Complexity: O(1)

일반적인 변수만 정의해서 썼기 때문에 1의 공간복잡도를 가진다.

 

 

다른 해결 방식

1. 좀 더 깔끔한 방식으로 푼 사람이 있어서 가져와봤다.

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head;
        
 # 순서 prev cur(홀수번째) adj(짝수번째) adj.next
 # 이를 prev adj cur adj.next 순서로 바꾸고자함.
        
        prev, cur, ans = None, head, head.next;  # prev(이전 노드) cur(현재 노드) ans(답)
        while cur and cur.next:                  # pair로 있을 때까지
            adj = cur.next                       # 뒤의 조정 대상
            if prev:
                prev.next = adj                 #이전 노드의 다음은 짝수번째 노드가 될 것.
            
            cur.next, adj.next = adj.next, cur;
            prev, cur = cur, cur.next;
        
        return ans or head;

 

 

Time Complexity:  O(N)

Node 전체의 순회가 이루어질 수 밖에 없기 때문에 N의 시간복잡도를 가진다.

 

Space Complexity: O(1)

일반적인 변수만 정의해서 썼기 때문에 1의 공간복잡도를 가진다.

 

 

문제 링크

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

Swap Nodes in Pairs - LeetCode