[파이썬 알고리즘] 8장 - 홀짝 연결 리스트 (leetcode 328)

https://leetcode.com/problems/odd-even-linked-list/

Odd Even Linked List - LeetCode

 

<문제>

연결 리스트를 홀수 노드 디음에 짝수 노드가 오도록 재구성하라.
(여기서 홀수 노드, 짝수 노드는 node안의 val이 아니라, node의 number)
공간 복잡도 0(1), 시간복잡도 o(n) 에 풀이하라.

 

<예제>

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

 

---

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def oddEvenList(head: ListNode) -> ListNode:
    if head is None:
        return None

    odd_node = head
    even_node = first_even_node = head.next
    while even_node and even_node.next:
        # even_node가 None이거나 even_node.next가 None이면 break
        # even_node의 다음 노드를 odd_node의 next로
        # even_node의 다다음 노드를 even_node의 next로
        odd_node.next, even_node.next = even_node.next, even_node.next.next
        odd_node = odd_node.next
        even_node = even_node.next

    odd_node.next = first_even_node
    return head

처음의 linked list

 

 

현재 홀수번째 노드는 다음 홀수번째 노드를 가리키도록,

현재 홀수번째 노드는 다음 짝수번째 노드를 가리키도록 연결을 만들어주고,

현재 홀수번째 노드를 다음 홀수번째 노드로, 현재 짝수번째 노드를 다음 짝수번째 노드로 변경

 

현재 홀수번째 노드는 다음 홀수번째 노드를 가리키도록,

현재 짝수번째 노드는 다음 짝수번째 노드가 없으므로 None을 가리키도록 만들어주고

현재 홀수번째 노드를 다음 홀수번째 노드로, 현재 짝수번째 노드를 다음 짝수번째 노드로 변경

 

현재 짝수 노드가 None이므로 while문 나오게 되고,

홀수번째 노드의 다음 노드로 첫 번째 짝수노드를 설정해준다.

이러면 끝이다.

 

 

노드의 개수가 짝수인 경우에도 위와 유사한 흐름이다.