[파이썬 알고리즘 인터뷰][연결리스트] 홀짝 연결 리스트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

연결 리스트의 홀수 노드 다음 짝수 노드가 오도록 재구성, 공간 복잡도 O(1), 시간 복잡도 O(n)

 

책에서 구현된 코드

def OddEvenList(self, head: ListNode) -> ListNode:
    if head in 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

 

기억해야할 기법

• 연결리스트의 탐색시, 항상 head를 따로 저장해두기
  
  • even_head = head.next
• odd와 even을 나누어서 해결
  • 포인터이므로 둘을 나눠 사용해도 공간복잡도에 영향이 없음

 

내가 구현한 코드

def oddEvenList(head: ListNode) -> ListNode:
    if head and head.next:
        odd = head
        even = even_root = head.next

        while even.next:
            odd.next = even.next
            odd = odd.next

            if odd.next:
                even.next = odd.next
                even = even.next
            else:
                even.next = None

        even.next = None
        odd.next = even_root

    return head

• 책에 나온 코드처럼 깔끔한 로직을 생각해보려했는데 생각해내지 못했다
  • while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
  • 끝에 odd 하나만 남는 경우
    - even의 next는 None이므로, 마지막 odd에 대한 처리 후 루프 종료
    - 마지막 odd를 처리했으므로, odd의 next를 even_root로 사용 가능
  • 끝에 odd와 even이 남는 경우
    - even의 next는 역시 None, 루프 종료
    - 뒤에 남은 값이 없으므로 odd의 next를 even_root로 바꾸면 끝