[리트코드] 328. 홀짝 연결 리스트 (Python)

Odd Even Linked List - LeetCode

문제

단방향 연결 리스트가 주어졌을 때 홀수 인덱스-> 짝수 인덱스로 연결해라

 

과정

1. 홀수 인덱스를 모두 연결한 뒤 짝수 인덱스를 모두 연결할 수 없으므로 홀수, 짝수 하나씩 연결한 후 다음 노드로 이동한다. 
2. 연결할 다음 노드가 없으면 반환한다.

입력

[1,2,3,4,5]

출력

[1,3,5,2,4]

 

풀이

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
        return None
    
        odd = head
        even = head.next
        even_head = head.next

        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next

        odd.next = even_head
        return head

 

한 줄씩 코드 해석해보기

if head is None:
    return None

• 연결 리스트가 비어있는 경우 None을 리턴해 예외처리를 해준다.

odd = head
even = head.next
even_head = head.next

• odd 변수에 head값을 넣어준다 
• even 변수에 head 다음 값을 넣어준다 
• head의 다음값을 저장해 놓을 even_head를 만든다. 
• ex) 1 -> 2 -> 3 -> 4 -> 5 인 경우 odd = 1 / even = 2 / even_head = 2

while even and even.next:
    odd.next, even.next = odd.next.next, even.next.next
    odd, even = odd.next, even.next

• even과 even.next에 값이 없을때까지 while문을 돌린다.
• 처음값을 넣은 odd의 다음값에 그 다음값을 넣고 even의 다음값에는 그 다음값을 넣는다
• 그 후 odd에 오드 다음 값을 넣고 even에 even다음값을 넣어준다.
• 즉, even은 순차적으로 이동하면서 짝수번째 노드를 가리키며, even_head는 짝수번째 노드들의 시작을 가리킨다.
• ex) 1 -> 2 -> 3 -> 4 -> 5 인 경우
      odd.next = odd.next.next = 1 -> 3
      even.next = even.next.next = 2 -> 4
      odd = odd.next = 1 -> 3 
      even = even.next = 2 -> 4

odd.next = even_head
return head

• odd와 even을 모두 연결했다면 홀수번째 노드들 다음으로 짝수번째 노드가 올 수 있도록 odd다음에 even_head가 오도록 만든다.
• 그 후 head를 반환한다.
• ex) 1 -> 2 -> 3 -> 4 -> 5 인 경우
      while문을 다 돌고 나서 
      odd = 1 -> 3 -> 5
      even = 2 -> 4
      odd.next 에 even_head값을 넣어주기 때문에
      head = 1 -> 3 -> 5 -> 2 -> 4