[리트코드] Odd Even Linked List(python)

리트코드, Odd Even Linked List_홀짝 연결리스트

TL;DR

• 연결리스트(Linked List)를 활용할 수 있는지

문제 분석

1. 주어진 연결리스트에 대해서 홀수 인덱스끼리 묶은 연결리스트와 짝수 인덱스끼리 묶은 연결리스트로 재정렬된 연결리스트를 반환하라.
2. 첫번째 노드부터 홀수, 두번째 노드부터 짝수로 가정한다.
3. 홀수와 짝수 내에서 입력에 주어진 순서를 유지해야 한다.
4. O(1)의 공간복잡도와 O(n)의 시간복잡도로 해결해야 한다.

 

- 1 : 해결해야 하는 문제 조건에 대해 설명하고 있다.

- 2 ~ 3 : 세부 조건에 대해서 말하고 있다. 입출력 형태 파트에서 이 조건에 대해서 살펴본다.

- 4 : 문제 해결 시 만족해야 하는 조건에 대해서 설명하고 있다. 리스트와 같은 변수를 따로 할당하여 문제를 해결해서는 안되며, 너무 많은 시간이 소모되서도 않된다.

입출력 형태

입출력 예시

 

- 문제 조건 2에 따라 홀수 인덱스 노드는 1, 3, 5이고 짝수 인덱스 노드는 2, 4이다.

- 문제 조건 3에 따라 다시 재정렬된 연결리스트에서 홀수 인덱스의 순서는 입력 노드의 순서인 1, 3, 5를 유지하고 있고 짝수 인덱스의 순서 역시도 입력 순서인 2, 4를 유지하고 있다. 5 -> 3 -> 1 -> 4 -> 2와 같이 입력과 다른 순서로 배치되면 안된다는 뜻이다.

풀이

# 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: ListNode) -> ListNode:
        if not head:
            return None
        
        odd, even = None, None
        answer = None
        
        # reverse odd and even
        while head and head.next: # 1
            odd, odd.next, even, even.next, head= head, odd, head.next, even, head.next.next
        if head:
            odd, odd.next = head, odd
            
        # merge odd and even
        while even and even.next: # 2
            answer, answer.next, even = even, answer, even.next            
        if even:
            answer, answer.next = even, answer
        while odd and odd.next: # 3
            answer, answer.next, odd = odd, answer, odd.next
        if odd:
            answer,answer.next = odd, answer

        return answer

 

- https://firsteast.tistory.com/35 문제에서 사용한 Runner 기법과 다중할당을 응용하여 문제를 해결하였다.

- 1. 다중 할당을 통해 홀수 인덱스 연결리스트와 짝수 인덱스 연결리스트를 나눈다.

    - 다중 할당의 성질에 의해 역순으로 각 홀수 인덱스 연결리스트와 짝수 인덱스 연결리스트가 배치되어 있다.

    - head에는 마지막 노드가 남아있으므로 해당하는 부분에 대한 처리를 조건문을 통해 해준다.

    - 이 코드를 거치게 되면 odd : 5 -> 3 -> 1 , even : 4 -> 2를 얻을 수 있다.

 

- 이제 얻어낸 홀수 인덱스 연결리스트와 짝수 인덱스 연결리스트를 하나로 합치면 된다. 다시 원래 순서대로 돌려야하므로 Runner 기법의 응용을 통해서 문제를 해결한다.

- 2. 짝수 인덱스 연결리스트가 뒤에 와야 하므로 먼저 시작한다. 이 과정을 거치면 정답 연결리스트는 2 -> 4가 된다.

- 3. 홀수 인덱스 연결리스트를 마저 합친다. 이 과정을 거치면 정답 연결리스트는  1 -> 3 -> 5 -> 2 -> 4가 된다.

- 하나의 연결리스트를 사용하였기 때문에 공간복잡도를 만족하고, 연결리스트를 순차적으로 조회하기 때문에 시간복잡도 또한 만족한다.

개선된 풀이

- 내가 풀이한 방법은 역순으로 홀수 인덱스와 짝수 인덱스 연결리스트를 각각 나눈 후 다시 합치는 과정을 거치기 때문에 문제에서 제시한 제한조건에 걸리지 않고 문제를 해결할 수 있었지만, 완전히 효율적인 방법이라고는 할 수 없다.

- 홀수와 짝수를 나누는 부분을 동시에 진행할 수 있다면 더 좋은 답안을 작성할 수 있을 것 같다.