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

생각해본것

1. 또 배열로 정렬해서 풀고 싶지만 이런 풀이는 좋지 못한 풀이라해서.. 다른 방식으로 풀어보자

2. 홀수 노드인것 뒤에 짝수 노드를 붙히면 되겠네

3. swap이란 걸 써볼까?

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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
        

구현은 아직 못했지만 책에 있는 내용이 머리속에 잘 들어왔다.

다른 풀이 법도 찾아봤는데 밑에 방법은 dummy를 쓴다.

이 방법도 익혀두면 좋을 것 같다. 연결 리스트는 dummy를 쓰면 간편해지고

더 시야를 넓게 쓸수 있을 것 같으니 dummy도 익히자!

def oddEvenList(self, head):
    dummy1 = odd = ListNode(0)
    dummy2 = even = ListNode(0)
    while head:
        odd.next = head
        even.next = head.next
        odd = odd.next
        even = even.next
        head = head.next.next if even else None
    odd.next = dummy2.next
    return dummy1.next