- Problem

1721. Swapping Nodes in a Linked List

- 첫 번째 풀이

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        vals = []

        while head:
            vals.append(head.val)
            head = head.next
        
        head = answer = ListNode()
        vals[k-1], vals[-k] = vals[-k], vals[k-1]

        for i in range(len(vals)):
            answer.val = vals[i]

            if i != len(vals) - 1:
                answer.next = ListNode()
                answer = answer.next

        return head

• 시간 복잡도: O(N) (N: head의 길이)
• 공간 복잡도: O(N)

- 두 번째 풀이

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur_node = head

        for _ in range(k-1):
            cur_node = cur_node.next
            
        left_swap_node = cur_node

        right_swap_node = head

        while cur_node.next:
            cur_node = cur_node.next
            right_swap_node = right_swap_node.next
        
        left_swap_node.val, right_swap_node.val = right_swap_node.val, left_swap_node.val

        return head

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

- 결과