[LeetCode] 1721. Swapping Nodes in a Linked List

김민우·2023년 5월 15일
0

알고리즘

목록 보기
187/189

- 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)

- 결과

profile
Pay it forward.

0개의 댓글