18. Odd Even Linked List

아현·2021년 3월 23일
0

Algorithm

목록 보기
19/400

리트코드

  • 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라.

  • 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라




1. 반복 구조로 홀짝 노드 처리


# 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 head is None:
            return None
        
        odd = head
        even = head.next
        even_head = head.next
        
        #반복하면서 홀짝 노드 처리
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
            
        #홀수노드의 마지막을 짝수 헤드로 연결
        odd.next = even_head
        return head
        
  • 이런 문제는 제약이 없을 경우 연결 리스트를 리스트로 바꾸고 파이썬 리스트가 제공하는 슬라이싱과 같은 다양한 함수를 사용하면 좀 더 쉽고 직관적이며 또한 빠르게 풀 수 있다.

    • 파이썬 내장 함수의 실행 속도가 훨씬 더 빠르기 때문이다.

    • But, 이러한 풀이 방식은 우아하지 않다.

  • 홀(odd), 짝(even) 각 노드를 구성한 다음 홀수 노드의 마지막을 짝수 노드의 처음과 이어주면 될 것 같다.

  • 입력 값을 다음과 같이 생각해보자.

  • 홀수 변수는 head이고, 짝수 변수는 head.next이다.

    • 짝수의 헤드는 head.next이므로, even_head = even = head.next로 일단 시작한다.
  • while을 통해서 루프를 돌면서 처리한다.

    • 첫 번째 반복 시 홀수 odd는 1 -> 3으로 연결되고, 3을 값으로 갖게 된다.
      짝수 even은 2->4가 되고, 4를 값으로 갖는다.

    • 두 번째는 3->5와 4->None이 되고, 마지막으로 5와 None이 남게 된다.

  • 다중할당

    odd.next, odd = odd.next.next, odd.next

    • 아쉽게도 가능하지 않다.

    • 첫 번째 반복의 경우 1->3이 되지만 odd는 2가 된다. 아직 odd는 head는 동일한 참조며, head.next가 2이기 때문이다.

    • 기대하는 결과는 1->3이 되고 odd가 3이되는 것인데, 이처럼 다중할당으로 처리하게 되면 서로 다른 결과가 된다.

    • 다만, 홀짝처리를 하나로 묶어서 다음과 같이 두 줄로 처리하는 다중 할당은 가능하다.

    odd.next, even.next = odd.next.next, even.next.next
     odd, even = odd.next, even.next
    • 이렇게 해서 끝까지 처리되면 홀수 odd는 5, 짝수 even은 None이 된다.
  • 이제 odd.next를 짝수의 헤드 even_head와 연결한다.

  • 그리고 head를 리턴한다


  • head는 1, even_head는 2가 되기 때문에, 앞서 처리된 내용을 바탕으로 1부터 결과를 쭉 나열해보면 1->3->5->2->4->None이 된다.

  • odd, even, even_head 등의 변수들은 n의 크기에 관계 없이 항상 일정하게 사용하기 때문에, 공간 복잡도 또한 O(1)으로 제약 조건을 만족한다.

profile
For the sake of someone who studies computer science

0개의 댓글