C++의 단일 순회에서 연결 목록의 두 번째 마지막 노드 찾기

이제 연결 목록에서 마지막 두 번째 요소를 가져오는 방법을 살펴보겠습니다. [10, 52, 41, 32, 69, 58, 41]과 같은 요소가 거의 없다고 가정하고 마지막 두 번째 요소는 58입니다.

이 문제를 해결하기 위해 두 개의 포인터를 사용하여 하나는 현재 노드를 가리키고 다른 하나는 현재 위치의 이전 노드를 가리키며 다음 현재 노드가 null이 될 때까지 이동한 다음 단순히 이전 노드를 반환합니다.

예시

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
      Node *next;
};
void prepend(Node** start, int new_data) {
   Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = NULL;
   if ((*start) != NULL){
      new_node->next = (*start);
      *start = new_node;
   }
   (*start) = new_node;
}
int secondLastElement(Node *start) {
   Node *curr = start, *prev = NULL;
   while(curr->next != NULL){
      prev = curr;
      curr = curr->next;
   }
   return prev->data;
}
int main() {
   Node* start = NULL;
   prepend(&start, 15);
   prepend(&start, 20);
   prepend(&start, 10);
   prepend(&start, 9);
   prepend(&start, 7);
   prepend(&start, 17);
   cout << "Second last element is: " << secondLastElement(start);
}

출력

Second last element is: 20