C++ 한 번의 순회로 연결 리스트의 뒤에서 두 번째 노드 찾기

이번 글에서는 연결 리스트(Linked List)에서 뒤에서 두 번째 요소를 구하는 방법을 알아보겠습니다. 예를 들어 리스트가 [10, 52, 41, 32, 69, 58, 41]과 같이 구성되어 있다면, 뒤에서 두 번째 요소는 58입니다.

접근 방법: 두 개의 포인터 활용

이 문제는 두 개의 포인터를 사용하면 리스트를 딱 한 번만 순회하면서 해결할 수 있습니다.

첫 번째 포인터(curr)는 현재 노드를 가리키고, 두 번째 포인터(prev)는 현재 노드의 이전 노드를 가리킵니다. 그런 다음 현재 노드의 다음 노드가 NULL이 될 때까지 두 포인터를 함께 앞으로 이동시킵니다. 순회가 끝나면 curr은 마지막 노드를, prev는 뒤에서 두 번째 노드를 가리키게 되므로, prev의 데이터를 반환하면 됩니다.

C++ 구현 예제

#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

코드 설명

prepend() 함수는 새 노드를 리스트의 맨 앞에 삽입하는 역할을 합니다. 따라서 위 예제에서는 15, 20, 10, 9, 7, 17 순서로 삽입했기 때문에 실제 리스트는 [17, 7, 9, 10, 20, 15]가 됩니다. 이 리스트에서 뒤에서 두 번째 요소는 20이며, 실행 결과와 일치합니다.

secondLastElement() 함수는 curr과 prev 두 포인터를 초기화한 뒤, curr->next가 NULL이 아닌 동안 반복하면서 두 포인터를 한 칸씩 전진시킵니다. 반복문이 종료되는 시점에 curr은 마지막 노드, prev는 뒤에서 두 번째 노드를 가리키므로 prev->data를 반환하면 원하는 값을 얻을 수 있습니다.

시간 복잡도

이 방법은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 공간은 포인터 두 개뿐이므로 공간 복잡도는 O(1)입니다. 참고로 리스트에 노드가 2개 미만인 경우에는 뒤에서 두 번째 노드가 존재하지 않으므로, 실제 코드에서는 이러한 예외 상황에 대한 처리를 추가하는 것이 안전합니다.