[leetcode / 24] Swap Nodes in Pairs


날짜: 2021년 8월 25일
카테고리: 연결 리스트
태그: Medium, 24, 파이썬

leetcode 206 - Swap Nodes in Pairs

입출력 예시

예제 입력예제 출력
head = [1,2,3,4][2,1,4,3]
head = [][]
head = [1][1]

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = root = ListNode(None)
        prev.next = head
        
        while head and head.next:
            point = head.next
            head.next = point.next
            point.next = head
            prev.next = point
            
            head= head.next
            prev= prev.next.next
        
        return root.next
파이썬 알고리즘 인터뷰 8-5

풀이 과정

  1. prevroot에 연결 리스트의 초기 값 저장
    prevhead를 다음 값으로 향하도록 함
    • 인접한 두 노드를 스왑하므로 현재노드와 다음노드가 존재할 때까지 반복
    • 2-1의 그림처럼 인접한 두 노드를 스왑 (동시에 경로도 꼬아 줘야 함)
    • pointhead의 다음에 올 값을 저장
    • head는 다음 값으로 point의 다음 값을 향하도록 함
    • point는 다음 값으로 head를 향하도록 함
    • prev는 다음 값으로 point를 향하도록 함
      - 2-2의 그림처럼 정리가 됨
  2. head를 앞으로 1칸 시프트하고 prev를 앞으로 2칸 시프트
  3. 2와 3을 headhead.next에 None이 들어갈 때까지 반복

반성

  • 그림을 그려야 비로소 이해되는 단계가 아닌 머리로 바로 이해가 될 때까지 알고리즘 문제를 반복하자




© 2021. by hminkim