Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 k 값을 기준으로 연결 리스트 노드를 재배열하는 프로그램

문제 개요

단일 연결 리스트(singly linked list)와 하나의 값 k가 주어졌을 때, 노드들을 다음 순서로 재배열하는 프로그램을 만들어 보겠습니다.

  • k보다 작은 값을 가진 노드들이 가장 먼저 옵니다.
  • k와 같은 값을 가진 노드들이 그다음에 옵니다.
  • k보다 큰 값을 가진 노드들이 마지막에 옵니다.

핵심 제약 조건은 각 그룹 안에서 노드들의 상대적인 순서가 그대로 유지되어야 한다는 점입니다. 즉, 안정적(stable)인 분할이 필요합니다.

예를 들어 입력이 L = [4, 3, 6, 6, 6, 10, 8]이고 k = 6이라면 출력은 [4, 3, 6, 6, 6, 10, 8]이 됩니다. 4와 3은 6보다 작아 앞쪽으로, 10과 8은 6보다 커서 뒤쪽으로 이동하지만 각 그룹 내부의 원래 순서는 변하지 않습니다.

접근 방법: 더미 헤드 3개로 세 개의 버킷 만들기

이 문제는 값이 0인 더미(dummy) 헤드 노드 3개를 만들어 각각 버킷 역할을 하게 하는 방식으로 깔끔하게 해결할 수 있습니다.

  • less_head: k보다 작은 노드를 모으는 리스트의 시작점
  • equal_head: k와 같은 노드를 모으는 리스트의 시작점
  • greater_head: k보다 큰 노드를 모으는 리스트의 시작점

더미 헤드마다 현재 끝을 가리키는 포인터(less, equal, greater)를 두고, 원본 리스트를 처음부터 끝까지 한 번 순회하면서 각 노드를 조건에 맞는 버킷에 차례로 연결합니다. 순회가 끝나면 세 개의 리스트를 앞에서부터 이어 붙이면 완성됩니다.

단계별 풀이 과정

  • less_head := 값이 0인 연결 리스트 노드 생성, less := less_head
  • equal_head := 값이 0인 연결 리스트 노드 생성, equal := equal_head
  • greater_head := 값이 0인 연결 리스트 노드 생성, greater := greater_head
  • cur := node (원본 리스트의 첫 번째 노드)
  • cur가 null이 아닌 동안 반복:
    • cur의 값이 k보다 작으면 → less 뒤에 같은 값을 가진 새 노드를 연결하고 less를 한 칸 전진
    • cur의 값이 k보다 크면 → greater 뒤에 새 노드를 연결하고 greater를 한 칸 전진
    • 그 외(값이 k와 같으면) → equal 뒤에 새 노드를 연결하고 equal을 한 칸 전진
    • cur := cur의 다음 노드
  • 순회 종료 후 less.next := equal_head.next 로 연결
  • equal.next := greater_head.next 로 연결
  • less_head.next 반환 (더미 헤드를 제외한 실제 결과 리스트)

파이썬 구현 코드

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

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


def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head


def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')


class Solution:
    def solve(self, node, k):
        # k 미만 / 같음 / 초과 세 그룹용 더미 헤드 생성
        less_head = less = ListNode(0)
        equal_head = equal = ListNode(0)
        greater_head = greater = ListNode(0)

        cur = node
        while cur:
            if cur.val < k:
                less.next = ListNode(cur.val)
                less = less.next
            elif cur.val > k:
                greater.next = ListNode(cur.val)
                greater = greater.next
            else:
                equal.next = ListNode(cur.val)
                equal = equal.next
            cur = cur.next

        # 세 개의 리스트를 하나로 이어 붙임
        less.next = equal_head.next
        equal.next = greater_head.next

        return less_head.next


ob = Solution()
L = make_list([4, 3, 6, 6, 6, 10, 8])
k = 6
print_list(ob.solve(L, k))

입력

[4, 3, 6, 6, 6, 10, 8], 6

출력

[4, 3, 6, 6, 6, 10, 8]

복잡도 분석

  • 시간 복잡도: O(n) — 리스트를 딱 한 번만 순회하므로 노드 수 n에 비례합니다.
  • 공간 복잡도: O(n) — 위 구현은 조건에 맞는 새 노드를 생성하지만, 기존 노드의 포인터만 다시 연결하도록 수정하면 추가 공간 없이 O(1)로 처리할 수도 있습니다.