Linked Lists:Get Node Value

주어진 연결 리스트(Linked List)에서 뒤에서부터 특정 인덱스에 해당하는 노드의 데이터 값을 찾는 알고리즘 문제입니다. 이 문제의 목표는 연결 리스트의 뒤에서부터 세어 나간 인덱스에 해당하는 노드의 데이터 값을 반환하는 것입니다.

연결 리스트는 데이터 요소(Node)로 이루어진 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 링크(또는 포인터)로 구성됩니다. 연결 리스트의 끝을 나타내는 노드는 다음 노드를 가리키는 링크가 없는 특별한 노드일 수 있습니다.

문제 설명:
문제의 입력으로는 연결 리스트의 시작 노드와 찾아야 할 뒤에서부터 세어 나가는 인덱스 position이 주어집니다. 이때, position에 해당하는 노드의 데이터 값을 반환해야 합니다.

알고리즘 절차:

연결 리스트를 순회하면서 노드를 세어 나갑니다.
연결 리스트의 끝까지 순회하면서 노드의 개수를 계산합니다.
연결 리스트의 총 노드 개수를 알고 있다면, 뒤에서부터 세어 나간 인덱스 position을 사용하여 목표 노드의 위치를 계산할 수 있습니다.
목표 노드의 위치에 도달하면 해당 노드의 데이터 값을 반환합니다.

int getNode(SinglyLinkedListNode* head, int positionFromTail) {
    int length = 0; // 연결 리스트의 길이를 저장하는 변수
    SinglyLinkedListNode* current = head;

    // 연결 리스트를 순회하면서 길이 계산
    while (current != nullptr) {
        length++;
        current = current->next;
    }

    // 뒤에서부터 세어 나간 위치 계산
    int positionFromHead = length - positionFromTail - 1;
    current = head;

    // 목표 위치에 도달할 때까지 순회
    for (int i = 0; i < positionFromHead; i++) {
        current = current->next;
    }

    // 목표 위치의 데이터 값을 반환
    return current->data;
}

 

연결 리스트를 역순으로 변경하여 연결 리스트의 시작 노드가 ret에 저장됩니다. 이것은 연결 리스트를 뒤에서부터 순회하기 위한 준비 단계입니다.
positionFromTail 값에 따라 ret 포인터를 해당 위치로 이동합니다. 이 위치는 뒤에서부터 세어 나가는 인덱스입니다.
ret 포인터가 가리키는 노드의 데이터 값을 반환하여 문제의 답을 얻습니다.

int getNode(SinglyLinkedListNode* llist, int positionFromTail) {
    SinglyLinkedListNode* current = llist; // 현재 노드를 가리키는 포인터
    SinglyLinkedListNode* prev = nullptr;  // 현재 노드의 다음 노드를 가리키는 포인터

    // 연결 리스트를 역순으로 변경
    while (current) {
        SinglyLinkedListNode* next = current->next; // 현재 노드의 다음 노드를 임시로 저장
        current->next = prev; // 현재 노드의 다음 노드를 이전 노드로 변경
        prev = current; // 이전 노드를 현재 노드로 업데이트
        current = next; // 현재 노드를 다음 노드로 이동
    }

    SinglyLinkedListNode* ret = prev; // 연결 리스트의 역순으로 변경된 시작 노드
    for (int i = 0; i < positionFromTail; i++) {
        ret = ret->next; // 목표 위치에 도달할 때까지 노드를 순회
    }

    return ret->data; // 목표 위치의 노드의 데이터 값을 반환
}