파이썬 알고리즘 인터뷰 - 17. 페어의 노드 스왑

 

<--- 리트코드 24. Swap Nodes in Pairs --->

# 문제. 연결 리스트를 입력받아 페어 단위로 스왑하라.

 

입력

1->2->3->4

출력

2->1->4->3

 

 

# 풀이

1. 값만 교환

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def swap_pairs(head):
  cur = head
 
  while cur and cur.next:
    cur.val, cur.next.val = cur.next.val, cur.val
    cur = cur.next.next
 
  return head
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
head = swap_pairs(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next

 

2. 반복 구조로 스왑

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def swap_pairs(head):
  root = prev = ListNode(None)
  prev.next = head
  while head and head.next:
    # b가 a(head)를 가리키도록 할당
    b = head.next
    head.next = b.next
    b.next = head
 
    # prev가 b를 가리키도록 할당
    prev.next = b
 
    # 다음번 비교를 위해 이동
    head = head.next
    prev = prev.next.next
 
  return root.next
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
head = swap_pairs(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next

 

3. 재귀 구조로 스왑

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def swap_pairs(self, head):
  if head and head.next:
    p = head.next
    # 스왑된 값 리턴 받음
    head.next = self.swap_pairs(p.next)
    p.next = head
    return p
  return head
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
 
head = swap_pairs(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next