Interview Practice 13 – Last Kth Node of Linked List

Question

Given a linked list, find the Kth last node in a linked list. The last 0th node is the tail node in the linked list.

Solution

Easy task. Construct 2 pointers: P1 and P2. First, both of them are set to head. Move P2 to the next Kth node.

Example

# node structure
class node:
    data = None
    next = None
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# get item
def get_item(head, k):
    pointer_1 = head
    pointer_2 = head
    for i in xrange(k+1):
        if pointer_2 is not None:
            pointer_2 = pointer_2.next
    while pointer_2 is not None:
        pointer_1 = pointer_1.next
        pointer_2 = pointer_2.next
    return pointer_1

# linked list
node_9 = node(9)
node_8 = node(8, node_9)
node_7 = node(7, node_8)
node_6 = node(6, node_7)
node_5 = node(5, node_6)
node_4 = node(4, node_5)
node_3 = node(3, node_4)
node_2 = node(2, node_3)
node_1 = node(1, node_2)

# main
head = node_1
print get_item(head, 0).data
print get_item(head, 9).data
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

ListNode* fun(ListNode *head,int k)
{
    pone = ptwo = head;
    for(int i=0;i<=k-1;i++)
        ptwo=ptwo->next;
    while(ptwo!=NULL)
    {
        pone=pone->next;
        ptwo=ptwo->next;
    }
    return pone;
}

int main()
{
    char c;
    head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    p = head;
    while(c !='0')
    {
        q = (ListNode*)malloc(sizeof(ListNode));
        q->data = c;
        q->next = NULL;
        p->next = q;
        p = p->next;
        c = getchar();
    }
    cout<<"---------------"<<endl;
    cout<<fun(head,2)->data<<endl;

    return 0;
}

/////////////////////////////
1254863210
---------------
2
Press any key to continue
////////////////////////////

Leave a Reply

%d bloggers like this: