[leetcode] 328. 홀짝 연결 리스트 (Odd Even Linked List)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

홀수와 짝수 노드의 순서는 주어진 리스트의 순서와 같아야한다.

 

 

입출력 예시

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

 

생각과정

리스트의 index(0)은 홀수이고 index(1)은 짝수이다. 그리고 다음 홀수와 짝수 노드는 한칸 건너뛴 노드에 있음.

그렇다면 head.next를 head.next.next로 바꿔주는 과정을 반복하면 되지 않을까?

 

풀이

접근 방식은 어느정도 맞았다. 역시 이번에도 구현을 하지 못해서 해설을 보게 되었다. 기존 코드는 바보같이 지워버려서 풀이의 코드밖에 남지 않았다... 

 

def oddEvenList(head: ListNode) -> ListNode:
    # 예외 처리
    if head is None:
        return None

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

    # even이 head.next 즉, 맨 뒤의 값이므로 even기준으로 while문을 돌린다.
    while even and even.next:
        # odd와 even의 다음
        odd.next, even.next = odd.next.next, even.next.next

        # odd와 even을 다음으로 옮겨준다.
        odd, even = odd.next, even.next

    odd.next = even_head

    return head

생각한 대로 홀수와 짝수 노드를 지정해준 다음, odd.next와 even.next를 한칸 건너뛴 노드로 바꿔주고 다음 노드로 옮겨가는 방식으로 해결된다. 내가 생각했던 부분에서 추가된 점은 odd와 even을 연결해주기 위해 even_head를 가지고 있다가 마지막에 odd.next와 even_head를 연결해주는 부분이다. 또, out of range에러가 뜨지 않게 예외처리를 해주는 걸 잊지 말자!

 

코드를 이해하기는 어렵지 않기에 주석에 적혀있는 것 만으로도 충분할거같아 자세한 설명은 생략한다!

 

 

(대충 자세한 설명은 생략한다는 짤)

 

---

마치며

자꾸 풀다가 해결이 안된 코드를 지워버리는데, 정리할 때마다 어떻게 구현에서 문제가 있었는 지 알 수가 없어서 답답했다. 다음부턴 틀리더라도 꼭 작성하던 코드를 남겨둬야겠다.