[파이썬 알고리즘] 8장 - 페어의 노드 스왑 (leetcode 24)

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

Swap Nodes in Pairs - LeetCode

<문제>

연결 리스트를 입력받아 페어 단위로 스왑하라 .
이 때 노드의 값을 바꾸는 게 아니라, 노드 그 자체가 변경되어야 한다.

 

<예시>

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

---

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# my solution
def swapPairs(head: ListNode) -> ListNode:
    new_head = ListNode()       # dummy node
    new_head.next = head
    cur_before = new_head       # 현재 노드의 이전 노드
    cur = cur_before.next       # 현재 노드

    while cur is not None and cur.next is not None:
        # cur이 None이거나 cur.next가 None이면 중지
        # 1. A - [B - C] - D -> A - [C - B] - D
        cur_next = cur.next  # C
        cur_before.next = cur_next  # A->C
        cur.next = cur_next.next if cur_next.next else None  # B->D
        cur_next.next = cur  # C->B

        cur_before = cur_before.next.next
        cur = cur_before.next
    return new_head.next

 

바꾸고자 하는 두 노드만 고려하는 게 아니라, 이전 노드와 이후 노드까지 고려해주어야 한다.

어떻게 연결해야 연결이 끊기지 않을 지 고민하면서 풀면 바로 해결되는 문제이다.