[해커랭크] Get Node Value (C++)

문제 링크: www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem?h_r=internal-search

Get Node Value | HackerRank

1. 주의할 점

- List의 수를 알고 있어야 한다

- Head의 포인터를 새로운 포인터가 저장하고 있어야 한다

 

2. 구현

- 2가지의 방법으로 풀었다

 

[List크기 구하기 + 앞에서부터 찾기]

- Head가 가리키는 값과 같은 곳을 가리키는 Node를 생성한다

- Cnt를 통해 Head에 연결된 Node의 개수를 계산한다

- 모두 계산한 이후, 배열은 첫 번째 index가 0이므로 (Cnt-1) -positionFromTail를 Cnt에 재할당하여 앞에서부터 몇번째 위치한 Data를 Val에 저장할지 계산한다

- Node에 연결된 Node를 앞에서부터 검사하면서 Cnt가 0이라면 Val에 해당 Data값을 할당하고 While문을 탈출한다

int getNode(SinglyLinkedListNode* head, int positionFromTail) {
    SinglyLinkedListNode* node = head;
    int cnt=0;
    while(head){
        cnt++;
        head = head->next;
    }
    cnt = (cnt-1)-positionFromTail;
    int val;
    while(node){
        if(cnt==0){ 
            val = node->data;
            break;
        }
        cnt--;
        node = node->next;
    }
    return val;
}

 

[투 포인터]

- Head와 같은 주소를 가리키는 포인터 node와 result를 생성한다

- 둘의 차이가 positionFromTail만큼 나도록 node를 전진시킨다

- node->next가 NULL을 가리킬때까지 While문을 반복하며 node와 result를 모두 다음 node로 옮긴다

- result->data를 출력시킨다

int getNode(SinglyLinkedListNode* head, int positionFromTail) {
    SinglyLinkedListNode* node = head;
    SinglyLinkedListNode* result = head;
    for(int i=0;i<positionFromTail;i++)
        node = node->next;
    while(node->next){
        node = node->next;
        result = result->next;
    }
    return result->data;
}