LeetCode 328. Odd Even Linked List (Python3)

 

안녕하세요. 죠쵸입니다.

오늘도 Linked List 관련 문제입니다. LeetCode 38 번 문제인 이번 문제는 난위도 Medium에 해당이 됩니다. 난위도 Medium 문제 중에서 비교적 쉬운 문제인 것 같습니다. 시간이 되시면 같이 한번 풀어 보아요~. 단기적인 목표는 LeetCode 100 문제를 풀어보면서 블로그에 포스팅하는 것입니다. 가능하면 하루에 한개 풀어보려고 하고 있는데, 생각만큼은 되지 않지만, 멈추지 않고 계속해 보려고 합니다. 비록 문제를 풀면서, 저뿐만 아니라, 함께 해 주시는 여러분에게도 도움이 되길 바랩니다.

 

#LeetCode 328. Odd Even Linked List(Description)

LeetCode 328번 문제는 Linked List를 입력 받아서, 홀수 번째 Node는 앞쪽으로 순차적으로 연결하고, 짝수 번째 Node의 경우 홀수 Node의 뒤에 이어서 순차적으로 연결하여 해당 Linked List를 반환하는 것입니다. 비교적 문제 자체가 직관적이지 만, 아래의 그림을 보면 더 이해하기 쉬울 것 같습니다. 제약 사항으로 O(1) 공간복잡도와 O(Nodes)의 시간복잡도 내에서 풀이 해야합니다.

 

 

 

#LeetCode 328. Odd Even Linked List(Solution)

 

문제의 풀이 방법은 홀수번째 Node 만 계속 연결하고, 짝수번째 Node는 따로 연결하는 것을 반복하고, 최종 홀수 Node의 마지막 Node의 Next에 짝수 Node의 시작 Node를 지정하고 홀수 Node의 시작 Node를 반환하였습니다.  Linked List에 대한 기본 개념을 알고 있다면, 문제 자체가 복잡하지 않아서, 코드도 비교적 간단 합니다. 아래의 코드를 참조 부탁 드립니다.

 

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __print_all__(self):
        while self:
            print(self.val, end=' ')
            self = self.next

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head

        odd_head = odd_cur = head
        even_head = even_cur = head.next

        while odd_cur.next and even_cur.next:
            odd_cur.next = even_cur.next
            odd_cur = odd_cur.next
            even_cur.next = odd_cur.next
            even_cur = even_cur.next

        odd_cur.next = even_head

        return odd_head

 

 

방문해 주셔서 감사합니다. 여러분의 공감하기(♥), 댓글과 구독은 저에게 힘이 됩니다.

이상으로 죠쵸였습니다.