LinkedList : Odd Even Linked List

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

LeetCode - The World's Leading Online Programming Learning Platform

 

싱글 링크드 리스트를 받아서

홀수노드끼리 쭉 잇고 그다음 짝수노드끼리 쭉 이어진 형태로 만들어야한다.

 

기본 원리는 간단하다.

어떤 노드 n이 그 다다음 노드를 가리키게 하면된다.

n.next = n.next.next

 

한가지 주의할 점은 이렇게만하면 리스트가 두개로 분리돼버린다는 것이다.

그래서 우리는 마지막 홀수노드를 첫 짝수노드로 이어줘야한다.

그러기 위해서 첫 짝수노드를 미리 저장해둔다.

마지막 홀수노드를 계속 업데이트해가며 리스트를 순회하다가 리스트가 끝나면 마지막 홀수노드를 첫 짝수노드로 이어주고 마무리하면된다.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        if not head:
            return None

        cur = last_odd = dummy.next
        first_even = cur.next
        is_odd = True

        while True:
            if is_odd:
                last_odd = cur

            if not cur.next:
                break

            tmp = cur.next
            cur.next = cur.next.next
            cur = tmp

            is_odd = not is_odd

        last_odd.next = first_even

        return dummy.next