<aside> 💬 lv1, 자료 구조

링크드 리스트 역순 출력

문제 설명

문자열로 주어진 숫자들을 링크드 리스트로 변환한 후, 이 링크드 리스트를 역순으로 출력하는 프로그램을 작성해주세요. 각 숫자는 공백으로 구분되며, 링크드 리스트의 각 노드는 Node 클래스로 구현해야 합니다. 링크드 리스트를 역순으로 만든 후, 변환된 링크드 리스트를 문자열 형태로 반환해주세요.

제한 사항

입출력 예

입력 (문자열) 출력 (역순 링크드 리스트 문자열)
"1 2 3 4 5" "5 4 3 2 1"
"9 8 7" "7 8 9"
"15 20 25" "25 20 15"

입출력 설명

입력된 문자열을 링크드 리스트로 변환하고, 이를 역순으로 만든 후 다시 문자열로 반환합니다.

</aside>

😺 풀이 1. 연결 리스트(Linked List) 구현

**#1 Node 클래스 정의**
class Node:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

**#2 반전 함수 정의**
def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

**#3 리스트 변환 함수 정의**
def list_to_linked_list(elements):
    head = None
    for element in reversed(elements):
        head = Node(element, head)
    return head

**#4 문자열 변환 함수 정의**
def linked_list_to_string(head):
    elements = []
    current = head
    while current:
        elements.append(str(current.value))
        current = current.next
    return " ".join(elements)

단계별 풀이 전략

  1. Node 클래스 정의

    Node 클래스는 연결 리스트의 각 노드를 나타내는 클래스입니다. 각 노드는 value라는 데이터 필드와 next라는 다음 노드를 가리키는 포인터 필드로 구성됩니다. __init__ 메서드를 통해 Node 객체를 생성할 수 있습니다.

  2. 반전 함수 정의

    연결 리스트를 반전시키는 함수입니다. 반전 과정에서는 prev, current, next_node 세 개의 포인터를 사용합니다. current 노드의 next 포인터를 이전 노드인 prev를 가리키도록 변경합니다. 반복적으로 포인터를 이동시켜 연결 리스트를 반전시킵니다.

  3. 리스트 변환 함수 정의

    파이썬의 기본 리스트를 연결 리스트로 변환하는 함수입니다. 리스트의 요소를 반대 순서로 반복하면서 새로운 노드를 생성합니다. 새로운 노드의 next 포인터를 이전에 생성된 노드로 설정합니다.

  4. 문자열 변환 함수 정의

    연결 리스트의 모든 노드 값을 문자열로 변환하는 함수입니다. current 포인터를 사용하여 연결 리스트를 순회하면서 각 노드의 값을 리스트에 추가합니다. 리스트의 모든 요소를 공백으로 구분하여 문자열로 반환합니다.

알아둬야 할 개념

연결 리스트(Linked List)

노드(Node)

포인터(Pointer)

반복자(Iterator)