#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct ListNode {
    int value;
    struct ListNode *next;
} listnode_t;

void addListTail(listnode_t **phead, int val)
{
    if (phead == NULL) {
        printf("phead NULL\n");
        return;
    }

    listnode_t *p = new listnode_t();
    p->value = val;
    p->next = NULL;
    
    if (*phead == NULL) {
        *phead = p;
    } else {
        listnode_t *pnode;
        pnode = *phead;
        while (pnode->next != NULL) {
            pnode = pnode->next;
        }

        pnode->next = p;
    }
}

void addListSort(listnode_t **phead, int val)
{
    listnode_t *pb, *pc;
    
    if (phead == NULL) {
        printf("phead NULL\n");
        return;
    }

    listnode_t *p = new listnode_t();
    p->value = val;
    p->next = NULL;

    if (*phead == NULL) {
        *phead = p;
    } else if (val < (*phead)->value){
        p->next = *phead;
        *phead = p;
    } else {
        pb = *phead;
        pc = pb->next;

        while (pc != NULL) {
            if (val < pc->value) {
                break;
            }
            pb = pc;
            pc = pc->next;
        }

        pb->next = p;
        p->next = pc;
    }
}

void delListNode(listnode_t **phead, int val)
{
    listnode_t *ptodel;
    listnode_t *pb, *pc;
    
    if (phead == NULL || *phead == NULL) {
        printf("invalid input...\n");
        return;
    }

    ptodel = NULL;
    
    if ((*phead)->value == val) {
        ptodel = *phead;
        *phead = (*phead)->next;
    } else {
        pb = *phead;
        pc = pb->next;

        while (pc != NULL) {
            if (pc->value == val) {
                break;
            }

            pb = pc;
            pc = pc->next;
        }

        if (pc != NULL && 
                pc->value == val) {
            ptodel = pc;
            pb->next = pc->next;
        }
    }

    if (ptodel != NULL) {
        ptodel->next = NULL;
        delete ptodel;
    }
}

listnode_t *mergList(listnode_t *phead1, listnode_t *phead2)
{
    listnode_t *phead;
    listnode_t *p1, *p2, *p;
    
    if (phead1 == NULL) {
        return phead2;
    } 

    if (phead2 == NULL) {
        return phead1;
    }

    p1 = phead1;
    p2 = phead2;
    
    if (p1->value < p2->value) {
        phead = p1;
        p1 = p1->next;
    } else {
        phead = p2;
        p2 = p2->next;
    }

    p = phead;

    while ((p1 != NULL) && (p2 != NULL)) {
        if (p1->value < p2->value) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }

        p = p->next;
    }

    if (p1 != NULL) {
        p->next = p1;
    }

    if (p2 != NULL) {
        p->next = p2;
    }

    return phead;
}

listnode_t *findKth(listnode_t *phead, unsigned int k)
{
    listnode_t *pa = NULL;
    listnode_t *pb = NULL;
    
    if (phead == NULL || k == 0) {
        printf("Invalid input\n");
        return NULL;
    }

    pa = pb = phead;

    while ((pa->next != NULL) && (k > 1)) {
        k--;
        pa = pa->next;
    }

    if (k > 1) {
        return NULL;
    }

    while (pa->next != NULL) {
        pa = pa->next;
        pb = pb->next;
    }

    return pb;
}

void printList(listnode_t *phead)
{
    listnode_t *p;
    if (phead == NULL) {
        printf("list empty!!!\n");
        return;
    }

    p = phead;
    while (p) {
        printf("%d--->", p->value);
        p = p->next;
    }
    printf("NULL\n");
}

int main()
{
    int val = 1;
    listnode_t *head = NULL;
    listnode_t *head2 = NULL;
    listnode_t *phead = NULL;
    
    while (val != 0) {
        scanf("%d", &val);
        //addListTail(&head, val);
        addListSort(&head, val);
        printList(head);
    }

    scanf("%d", &val);
    phead = findKth(head, val);
    if (phead == NULL) {
        printf("node not exist!\n");
        return 0;
    }
    printf("the Kth node value is %d\n", phead->value);

#if 0
    val = 1;
    printf("start inpurt list2:\n");
    while (val != 0) {
        scanf("%d", &val);
        //addListTail(&head, val);
        addListSort(&head2, val);
        printList(head2);
    }

    phead = mergList(head, head2);
    printList(phead);

    while (1) {
        scanf("%d", &val);
        delListNode(&head, val);
        printList(head);
    }
#endif

    return 0;
}