18. Odd Even Linked List

🎯 leetcode - 328. Odd Even Linked List

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 18번 문제
- 홀수번째 노드들이 먼저 오고 짝수노드가 그 다음에 오도록 구성된 연결리스트 만들기
- 공간복잡도는 O(1), 시간복잡도는 O(n)에 풀이할 수 있는 방법은?

📌 날짜

2020.01.14

📌 시도 횟수

1 try

💡 Code

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 예외 처리
        if head is None:
            return head
            
        even_root = even_curr = ListNode(0)
        root, prev = head, head
        
        while head and head.next:
            even_curr.next = head.next  # 0 -> b
            head.next = head.next.next  # a -> c
            
    	    # 이동시키기
            prev, head, even_curr = head, head.next, even_curr.next
            
        # even_curr의 끝을 끊어주기    
        even_curr.next = None
			
        # 만약 초기 노드 개수가 홀수개라면 head != None이므로...
        if head:
            head.next = even_root.next
        # 만약 초기 노드 개수가 짝수개라면 head는 None이므로
        # head 바로 앞의 노드인 prev 뒤에 짝수 연결리스트를 이어줌
        else:
            prev.next = even_root.next

        return root

💡 문제 해결 방법

• 연결리스트를 차례대로 순회하면서 짝수번째 노드들을 차례대로 끊어냈다.
• 그리고 even_root를 루트로 하는 새로운 (짝수)연결리스트를 만들었다.
• 모든 노드들을 다 순회하면 홀수번째 노드들만 남은 연결리스트의 끝에 짝수 노드들의 연결리스트를 연결했다.
• 그림으로 표현하면 아래 그림의 과정과 같다.
  
  
  
  
  
  

💡 새롭게 알게 된 점

- 이제 조금씩 연결리스트를 어떻게 다루어 풀 지에 대한 감이 생기는 것 같다!

• 
• 🥰💯

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 반복 구조 활용하기

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 예외 처리
        if head is None:
            return head

        odd = head
        even = head.next
        even_head = head.next

        # 반복하면서 홀/짝 노드 처리하기
        while even and even.next:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next

        odd.next = even_head
        return head

+ 참고로

• 위의 while문 안의 코드를 다중할당으로 구현하면 다음과 같다.

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 예외 처리
        if head is None:
            return head

        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

💡 새롭게 알게 된 점

- 내 풀이랑 비슷한 듯 싶은데 이 풀이가 코드 가독성이 더 좋은 것 같다.

---