Swap Nodes in Pairs [leetcode]

문제

문제 풀이 정리

 

의외로 머리속에서 정리가 안되던 문제였다.

그림을 보면 알겠지만 짝수 일때만 자리를 바꿔줘야 한다. 하지만 List(배열) 이 아니고 Linked List 이기 때문에

인덱스로 접근할 수 없다. 그래서 even_flag를 만들어서 마치 짝수일때만 동작할 수 있도록 한다.

 

현재 위치가 짝수일 때와 홀수일 때 로직이 다른데 적어보자.

홀수일 때

• 현재 노드는 이전 노드로 지정한다. (prev = curr)
• 현재 위치를 다음 노드로 옮긴다.(혹은 지정한다.) (curr = curr.next)
• 짝수 플래그를 true로 변경한다.

if even_flag == False:
  prev = curr
  curr = curr.next
  even_flag = True

짝수일 때

• 이전 노드의 next를 현재 노드의 next로 치환한다.
  현재 노드 2, (1→2→3 ⇒ 1→3, 2→3)
• 현재 노드의 next를 이전노드로 치환한다.
  현재 노드 2, (2→3 ⇒ 2→1, 결과적으로 2→1→3)
  
  
• 다음 노드 위치를 지정한다.
  (원래는 curr=curr.next 이여야 하지만, 이전 노드의 다음이 실제 다음 노드가 됐으므로 curr=prev.next)

else: # even_flag == True:
 prev.next = curr.next #이전 노드의 next를 현재 노드의 next로 치환한다.
 curr.next = prev #현재 노드의 next를 이전노드로 치환한다.
 curr = prev.next #다음 노드 위치를 지정한다.

그런데 짝수일때 주의 점이 있다.

처음 1→2→3 의 노드를 자리바꿈 할때는 위 로직대로 동작하는게 맞지만

이후 1→3→4 일 경우, 위 로직대로 동작시 2→1→3 과 4→3 으로 (1→3 의 연결을 고려 하지 않기 때문)

쪼개지게 된다.

 

첫번째 짝수로직 다음에 실행되는 짝수로직에서는

prev_before | prev | curr(현재) ⇒ prev_before | curr | prev 로 만들어줄 필요가 있다.

 

위 짝수로직에서

다음 노드 위치를 지정하면 (curr = prev.next) 현재 위치는 자동적으로 prev 값이 된다.

그렇다면 4 위치에서 prev_before는 1이 되므로 prev_before는 현재 위치인 1 이 된다.

 

설명하면서도 이게 무슨 소리 인지 싶어서 숫자로 써본다

1→2→3→4

2 위치에서

1→3, 2→1 로 위치 지정을 마치면 2→1→3→4

현재 curr가 가리키는 위치는 curr=prev(=1).next로 3,

그럼 4 위치에 왔을때는 3 이전의 값(1) 이 되어야 하니 prev_before는 1 (=prev) 가 되는 것이다.

4 위치에 왔을때는 4→3 으로 자리를 바꾸기 전, 1→3의 연결을 끊고 1→4 로 먼저 변경한 뒤 자리를 바꾼다.

if prev_before != None: # 지정된 prev_before가 있다면
  prev_before.next = curr #(ex.1->3->4 에서 1->4 로 변경)

#짝수로직 실행               
prev.next = curr.next
curr.next = prev
curr = prev.next

prev_before = prev # prev_before 지정

또한 2→1→4→3 으로 반환하기 위해서는 처음 시작을 지정할 필요가 있는데(start)

처음 짝수로직을 실행할때 1→2 에서 2→1 로 시작점이 바뀌므로 start_flag를 세워 시작점을 지정해준다.

if start_flag == False:
  start = curr
  start_flag = True

전체 코드로 보자

코드

# 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]:
        
        even_flag = False
        curr = head
        prev = None
        prev_before = None
        start_flag = False
        start = None
        while curr != None:
            if even_flag == False:
                prev = curr
                curr = curr.next
                even_flag = True
            else:
                if start_flag == False:
                    start = curr
                    start_flag = True
                    
                if prev_before != None:
                    prev_before.next = curr
                    
                prev.next = curr.next
                curr.next = prev
                curr = prev.next
                
                prev_before = prev
                even_flag = False
        
        
        if start_flag == False:
            start = head
        return start

결과는