[leet24]linked list 앞에 dummy node를 붙여 조건을 통일하기

leetcode 24. swap nodes in pairs

Dummy란?

Linked List에서 head(or root) 앞에 추가로 붙여주는 노드를 dummy라 부르곤 한다. 붙이는 이유는 조건문을 단순하게 만들어주기 위해서이다. 말로 설명하는 것보다는 그림으로 이해하는 게 빠를 것 같아서 준비했다.

이 그림은 아래 문제를 풀기 위한 과정이다. 1-2-3-4로 이어지는 linked list에서 두개씩 쌍을 지어 순서를 바꾸는 문제이다. 만약 Dummy가 없다면, 두 개씩 끊어서 작업을 할 때 1->4로 이어지는 edge를 head인 2에서는 구현할 수가 없다. 이 엣지는 뒤로 리스트가 이어질 때마다 계속 반복되는데 처음 부분에서는 존재하지 않기 때문에 첫 두 노드의 위치를 바꿀 때와 이후 작업들에서 코드가 다르게 들어가야 한다. 즉, if문이 추가로 들어가야 한다.
Dummy로 0을 추가해주면 어떨까? 모든 두 쌍 작업들이 같은 코드로 수행될 수 있을 것이다. 마지막에 2를(dummy.next) return 해주면 아무 문제가 없다.

Question

연속한 한 쌍의 노드들의 위치를 바꿔주는 문제이다. 쌍이 이뤄지지 않을 경우(홀수일 경우)엔 그냥 그대로 출력하면 된다. 1->2->3은 2->1->3이 된다.

Solution

PSEUDO
use dummy(head node) not to use if code

• start = Node(0) # dummy
• cur = start
• start.next = head
• while cur.next and cur.next.next:
  one = cur.next
  two = cur.next.next
  cur.next = two 0 -> 2
  one.next = two.next 1 -> 3
  two.next = one 2 -> 1
  cur = one 0 -> 2 -> 1 -> 3, cur: 1
  return start.next # dummy.next 출력

def swapPairs(head):
    if not head:
        return head
    if not head.next:
        return head
    
    start = ListNode(0)
    start.next = head
    cur = start

    while cur.next and cur.next.next:
        one = cur.next
        two = one.next
        cur.next = two
        one.next = two.next
        two.next = one
        cur = one
    
    return start.next

github