파이썬 알고리즘 인터뷰 - 18. 홀짝 연결 리스트

 

<--- 리트코드 328. Odd Even Linked List --->

# 문제: 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간복잡도 O(1), 시간복잡도 O(n)에 풀이하라.

 

입력

1->2->3->4->5->NULL

출력

1->3->5->2->4->NULL

 

입력

2->1->3->5->6->4->7->NULL

출력

2->3->6->7->1->5->4->NULL

 

 

# 풀이

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

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def odd_even_list(head):
  if head is None:
    return
  
  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
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
list5 = ListNode(5)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
list4.next = list5
 
head = odd_even_list(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next