뒤에서 k번째 노드는 무엇일까요?
이번에는 연결리스트의 응용 문제를 풀어보겠습니다. 연결리스트가 하나 주어졌을 때 해당 연결 리스트의 뒤에서 k번째 노드의 값은 무엇일지 알아낼 수 있을까요? 예를 들어, 9->8->4->14->5 라는 리스트가 주어질 때 뒤에서 2번째 노드를 출력하라고 하면 14가 출력이 되어야 합니다.
연결리스트가 이미 만들어져 있다고 가정하고, 아래와 같은 함수가 주어졌을 때 뒤에서 k번째 노드를 출력할 수 있을까요?
typedef struct node{
int data;
struct node* next;
} Node;
void append(Node* head, int data) {
// 이 부분을 작성해 주세요!
}
int getLastNode (Node* head, int k) {
// 이 부분을 작성해 주세요!
}
void printList(Node* head) {
// 이 부분을 작성해 주세요!
}
int main() {
Node* head = (Node*)malloc(sizeof(Node));
append(head, 9);
append(head, 8);
append(head, 4);
append(head, 14);
append(head, 5);
printList(head);
printf("\\n%dth last node is %d\\n", 2, getLastNode(head, 2));
}
main 함수에는 정렬된 연결 리스트 1개가 미리 만들어져 있다고 가정합니다. 여러분이 작성하신 함수 getLastNode 함수에 main 함수에서 작성된 연결 리스트와 k를 파라미터로 주었을 때 뒤에서 k 번쨰 노드의 값이 나올 수 있을까요?
입력값:
미리 작성된 연결리스트와 k번째를 지칭하는 파라미터, 예들 들어 9->8->4->14->5 라는 리스트가 main 함수에 작성되어 있고, main 함수에서 해당 리스트와 k=2로 getLastNode를 호출
출력값:
9 8 4 14 5
2th last node is 14
3. 핵심 개념
#연결리스트 #리스트 삽입 #Slow Pointer #Fast Pointer