[leetcode / 24] Swap Nodes in Pairs
in Problem Solving on leetcode
날짜: 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
풀이 과정
prev
와root
에 연결 리스트의 초기 값 저장
prev
가head
를 다음 값으로 향하도록 함- 인접한 두 노드를 스왑하므로 현재노드와 다음노드가 존재할 때까지 반복
- 2-1의 그림처럼 인접한 두 노드를 스왑 (동시에 경로도 꼬아 줘야 함)
point
에head
의 다음에 올 값을 저장head
는 다음 값으로point
의 다음 값을 향하도록 함point
는 다음 값으로head
를 향하도록 함prev
는 다음 값으로point
를 향하도록 함
- 2-2의 그림처럼 정리가 됨
head
를 앞으로 1칸 시프트하고prev
를 앞으로 2칸 시프트- 2와 3을
head
와head.next
에 None이 들어갈 때까지 반복
반성
- 그림을 그려야 비로소 이해되는 단계가 아닌 머리로 바로 이해가 될 때까지 알고리즘 문제를 반복하자