/ cha

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 ////////////////////////////