파이썬 알고리즘 인터뷰 18번 짝수 홀수 연결 리스트 (리트코드 328번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

처음에 문제 대충 보고 짝수 값, 홀수 값 따로 분리하라는 문제인줄 알았다.

알고 보니 index를 기준으로 하라는 것이었다…

Solution

# Definition for singly-linked list.
from typing import Optional

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

class Solution:
    def set_node(self, head, idx, odd_pointer, even_pointer):
        if head is None:
            return even_pointer

        if idx % 2 == 0:
            even_pointer.next = ListNode(val=head.val)
            even_pointer = even_pointer.next
        else:
            odd_pointer.next = ListNode(val=head.val)
            odd_pointer = odd_pointer.next

        even_pointer = self.set_node(head.next, idx + 1, odd_pointer, even_pointer)
        return even_pointer

    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        odd_start, even_start = ListNode(), ListNode()
        even_pointer = self.set_node(head, 0, odd_start, even_start)

        even_pointer.next = odd_start.next
        return even_start.next

현재 노드의 인덱스 기준으로 짝수, 홀수를 나누었다.

여기서 새로운 노드를 만들 때 기존의 head를 가져다가 쓰면 안되고 해당 val의 값을 가지고 있는 새로운 노드를 생성해서 써야한다. 그냥 쓰면 현재 head의 뒤에 남은 연결 리스트가 딸려서 오게 된다.