[코딩인터뷰 완전정복] 2.2 뒤에서 K번째 원소 구하기

Q : 단방향 연결 리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라.

// linked_list.h
#include <iostream>

struct node {
	int data;
	node *next;
};

class linked_list {
private:
	node *head, *tail;
public:
	linked_list() {
		head = NULL;
		tail = NULL;
	}

	void add_node(int n) {
		node *temp = new node;
		temp->data = n;
		temp->next = NULL;
		if (head == NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = tail->next;
		}
	}

	node* first() {
		return head;
	}
};

#include <iostream>
#include "LinkedList.h"

int SearchKthNode(linked_list list, int k) {
	node *front, *end;
	front = end = list.first();

	for (int i = 0; i < k; i++) {
		end = end->next;
		if (end == NULL) return front->data;
	}

	while (end != NULL) {
		end = end->next;
		front = front->next;
	}

	return front->data;
}

int main() {
	linked_list list;
	list.add_node(1);
	list.add_node(2);
	list.add_node(1);
	list.add_node(5);
	list.add_node(4);
	list.add_node(4);
	list.add_node(1);
	list.add_node(5);

	int K;
	scanf_s("%d", &K);
	printf("%d\n", SearchKthNode(list , K));
}

2개의 노드 포인터를 만들고 거리를 k만큼 벌려놓는다.

그 후 뒤쪽에 있는 노드가 NULL이 될 때까지 (리스트의 끝까지) 2개의 포인터를 전진시킨다.

이때 앞쪽에 있는 노드가 뒤에서 k번째 노드가 된다.