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

파이썬(Python)으로 연결 리스트에서 특정 값의 마지막 등장 노드 제거하기

문제 개요

단일 연결 리스트(singly linked list)와 하나의 값 target이 주어졌을 때, 리스트에서 target이 마지막으로 등장하는 노드만 제거하는 것이 목표입니다.

예를 들어 입력 리스트가 [5,4,2,6,5,2,3,2,4,5,4,7]이고 target = 5라고 하겠습니다. 5는 총 세 번(앞에서 세 번째, 여섯 번째, 열 번째 위치) 등장하는데, 이 중 마지막 등장 하나만 제거하므로 결과는 다음과 같습니다.

[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7]

해결 접근 방식

이 문제는 리스트를 딱 한 번만 순회하면서 O(n) 시간 복잡도로 해결할 수 있습니다. 핵심은 두 개의 포인터를 활용하는 것입니다.

  • k : 현재 순회 중인 노드의 바로 앞 노드(이전 노드)를 추적합니다.
  • prev : target 값을 가진 노드가 발견될 때마다, 그 노드의 바로 앞 노드를 갱신하여 기록합니다.
  • found : target이 리스트에 실제로 존재했는지 여부를 나타냅니다.

순회 도중 target을 만날 때마다 prev를 갱신하기 때문에, 순회가 끝난 시점에는 prev가 자연스럽게 마지막 등장 노드의 직전 노드를 가리키게 됩니다.

알고리즘 단계

  1. head에 시작 노드를 저장합니다.
  2. k와 prev는 null로, found는 False로 초기화합니다.
  3. node가 null이 아닌 동안 다음을 반복합니다.
    • 현재 노드의 값이 target과 같으면 found를 True로 설정하고 prev에 k를 저장합니다.
    • k에 현재 노드를 저장한 뒤, node를 다음 노드로 이동시킵니다.
  4. found가 False라면 target이 없다는 뜻이므로 리스트를 변경하지 않고 head를 그대로 반환합니다.
  5. prev가 null이라면 마지막 등장 노드가 곧 헤드라는 의미이므로 head.next를 반환합니다.
  6. 그 외의 경우 prev.next를 prev.next.next로 변경해 마지막 등장 노드를 건너뛴 후 head를 반환합니다.

구현 예제

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, target):
        head = node
        k = None
        prev = None
        found = False
        while node:
            if node.val == target:
                found = True
                prev = k
            k = node
            node = node.next
        if not found:
            return head
        if not prev:
            return head.next
        prev.next = prev.next.next
        return head


ob = Solution()
L = make_list([5, 4, 2, 6, 5, 2, 3, 2, 4, 5, 4, 7])
target = 5
print_list(ob.solve(L, target))

입력

[5,4,2,6,5,2,3,2,4,5,4,7], target = 5

출력

[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7]

동작 원리 상세 설명

코드에서 주목할 부분은 if node.val == target: 블록 안의 prev = k입니다. k는 항상 현재 노드 바로 앞의 노드를 가리키므로, target을 새로 발견할 때마다 prev가 덮어써집니다. 결국 순회가 종료되면 prev에는 마지막 등장 노드의 이전 노드만 남게 됩니다.

  • target이 리스트에 없으면 아무 노드도 제거하지 않고 원본 리스트를 그대로 반환합니다.
  • 마지막 등장 노드가 헤드(첫 번째 노드)라면 prev가 None이므로, 두 번째 노드인 head.next를 새로운 헤드로 반환합니다.
  • 그 외의 경우에는 prev.next = prev.next.next 한 줄로 해당 노드를 연결 리스트에서 깔끔하게 분리합니다.

복잡도 분석

리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 포인터 변수 세 개만 사용하므로 공간 복잡도는 O(1)입니다. 리스트 전체를 배열로 변환하거나 두 번 순회하는 방식보다 효율적인 접근입니다.