[부스트 코딩 뉴비 챌린지 2020] week6_미션04 : 연결 리스트 뒤에서 k번째 노드 찾기

✔︎ 미션 4.

1. 미션 제목
뒤에서 k번째 노드는 무엇일까요?

 

2. 지시문

이번에는 연결리스트의 응용 문제를 풀어보겠습니다. 연결리스트가 하나 주어졌을 때 해당 연결 리스트의 뒤에서 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

 

---

 

#include <stdio.h>
#include <stdlib.h> //malloc()

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

Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    if(!node){
        printf("failed to create node\n");
        exit(0);
    }
    node->data = data;
    node->next = NULL;
    return node;
}

void append(Node* head, int data) {
    Node *node = createNode(data);
    Node *tmp = head;

    while(tmp->next != NULL) {
        tmp = tmp->next;
    }
    tmp->next = node;

    printf("%d is appended. \n", node->data);
}

int getLastNode (Node* head, int k) {
    Node* front = head;
    Node* rear = head;

    while(--k != 0)
        rear = rear->next;

    while(rear->next != NULL){
        front = front->next;
        rear = rear->next;
    }
    return front->data;
}

void printList(Node* head) {
    printf("printList: ");

    while(head->next != NULL){
        head = head->next;
        printf("%d ", head->data);
    }
    printf("\n");
}

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));
    while(head->next == NULL){
        Node* tmp = head;
        head = head->next;
        free(tmp);
    }
}

 

설명 주석을 달은 코드

#include <stdio.h>
#include <stdlib.h> //malloc()

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

Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    if(!node){  //메모리 문제로 node가 만들어지지 않았는지 확인
        printf("failed to create node\n");
        exit(0);    //node가 만들어지지 않았다면 종료
    }
    node->data = data;
    node->next = NULL;
    return node;
}

void append(Node* head, int data) {
    Node *node = createNode(data);  //입력된 data를 가진 노드 생성
    Node *tmp = head;   //마지막 노드인지 확인할 노드

    while(tmp->next != NULL) {  //tmp를 head에서부터 한 칸씩 전진시켜 마지막 노드에서 멈춤
        tmp = tmp->next;
    }
    tmp->next = node;   //마지막 노드인 tmp 뒤에 새로운 node를 이음

    printf("%d is appended. \n", node->data);
}

int getLastNode (Node* head, int k) {
    // front와 rear는 거리가 k만큼 띄워진 노드. front --(+k)--> rear
    // 두 노드는 head에서부터 시작
    Node* front = head;
    Node* rear = head;

    while(--k != 0)    //k-1부터 ~ 1까지 (k-1)번 반복함
        rear = rear->next;  // k-1만큼 rear를 뒤로 이동

    //rear이 마지막 노드가 될 때까지 front와 rear이 함께 한 칸씩 뒤로 이동
    while(rear->next != NULL){
        front = front->next;
        rear = rear->next;
    }
    //rear가 마지막 노드일 때 front가 뒤에서 k 번째 노드가 됨.
    return front->data;
}

void printList(Node* head) {
    printf("printList: ");

    while(head->next != NULL){  // 마지막 노드가 될 때까지 계속 한 칸씩 뒤로 이동하여 해당 노드 속 값을 출력
        head = head->next;
        printf("%d ", head->data);
    }
    printf("\n");
}

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));

    //할당받은 메모리를 해제함
    while(head->next == NULL){
        Node* tmp = head;
        head = head->next;
        free(tmp);
    }
}