[LeetCode] 24. Swap Nodes in Pairs

말하는 감자·2024년 12월 5일

leetcode linked list python recursion 리트코드 연결 리스트 재귀 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

28/32

1. 오늘의 학습 키워드

Linked List
Recursion

2. 문제: 24. Swap Nodes in Pairs

단계: Medium
주제: Linked List, Recursion
출처: https://leetcode.com/problems/swap-nodes-in-pairs/description/

Description

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

3. 문제 풀이

Step1. 문제 이해하기

주어진 연결 리스트에서 인접한 두 노드마다 위치를 교환하고, 변경된 연결 리스트를 반환하는 문제입니다.

인접한 두 노드마다 서로의 next 노드를 변경하면 될 것으로 보입니다. 입출력을 보도록 하겠습니다.

Input:
- 입력으로 주어지는 연결 리스트의 노드 개수는 0이상 100이하입니다.
- 노드 순회를 1번 진행하면 구현이 될 것 같아서 시간 복잡도 상으로 충분히 여유 있습니다.
Output:
- 변경된 연결리스트를 반환합니다.

Step2. 문제 분석하기

연결 리스트가 있을 때, 현재 노드와 현재 노드의 다음 노드를 계속 교환해가면서 진행하기 때문에, 반복문과 재귀 방법을 사용할 수 있습니다. 방법이 바로 떠올랐네요!

바로 코드 설계를 진행해보도록 하겠습니다.

Step3. 코드 설계

이 문제를 해결하기 위해, 반복문과 재귀를 사용한 두 가지 접근 방식을 설계합니다.

반복문 설계

초기화:
- 더미 노드(dummy node): 연결 리스트의 앞에 임의의 노드를 추가하여 리스트의 시작점이 바뀌는 경우를 깔끔하게 처리합니다.
- prev 포인터를 더미 노드로 초기화합니다.
두 노드씩 교환:
- 현재 노드(first)와 그 다음 노드(second)를 찾습니다.
- prev의 next를 second로 설정하여 두 노드의 위치를 변경합니다.
- first.next와 second.next를 적절히 설정하여 연결을 유지합니다.
다음 노드로 진행:
- prev를 한 쌍의 마지막 노드(first)로 이동시켜 다음 쌍을 처리합니다.
반복 종료:
- 리스트의 끝에 도달하면 반복을 종료하고, 더미 노드의 next를 반환합니다.

재귀 설계

기저 조건:
- 리스트가 비어 있거나 노드가 하나뿐이면 더 이상 교환할 필요가 없으므로 해당 노드를 반환합니다.
두 노드 교환:
- 현재 노드(first)와 다음 노드(second)를 식별합니다.
- first.next를 재귀 호출을 통해 반환된 다음 결과로 설정합니다.
- second.next를 first로 설정하여 두 노드의 위치를 변경합니다.
결과 반환:
- 변경된 second를 반환하여, 재귀 호출의 상위 호출에서 사용할 수 있도록 합니다.

Step4. 코드 구현

반복

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# 2. iterative
    def swapPairs(self, head):
        # https://leetcode.com/problems/swap-nodes-in-pairs/submissions/1470789178
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(next=head)
        prev = dummy

        while prev.next and prev.next.next:

            first = prev.next
            second = prev.next.next

            prev.next = second
            first.next = second.next
            second.next = first

            prev = first
        return dummy.next

코드 설명:
- 더미 노드를 활용하여, head가 교환되는 경우를 포함한 모든 상황을 간단히 처리합니다.
- 반복문 내에서 두 노드를 식별하고 연결 관계를 변경합니다.
- prev 포인터를 갱신하여 다음 쌍을 처리합니다.
시간 복잡도:
- 리스트의 각 노드를 한 번씩 방문하므로 $O(n)$ 입니다.
결과: https://leetcode.com/problems/swap-nodes-in-pairs/submissions/1470789178

재귀

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    # # 1. recursion
    def swapPairs(self, head):
        # https://leetcode.com/problems/swap-nodes-in-pairs/submissions/1470802663
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not head or not head.next:
            return head

        first = head
        second = head.next

        first.next = self.swapPairs(second.next)
        second.next = first

        return second

코드 설명:
- 재귀적으로 리스트를 순회하면서, 두 노드씩 교환합니다.
- first와 second를 식별하고 위치를 변경한 뒤, 다음 노드로 재귀 호출을 진행합니다.
- 반환된 second를 결과로 사용합니다.
시간 복잡도:
- 각 노드를 한 번씩 방문하므로 $O(n)$ 입니다.
결과: https://leetcode.com/problems/swap-nodes-in-pairs/submissions/1470802663