CareerCup

Take two pointers initialise second pointer after moving first pointer n positions so when first pointer will be at last position second pointer will be at nth last position

- Anonymous March 03, 2013 | Flag Reply

traverse linked list once to find the length of the LL.

then move along the LL, length - n - 1 times to reach the nth last node.

- manishi.singh March 01, 2013 | Flag Reply

I think this should work, not tested though:

node *findLastNth(node *head, int n){
    node *temp = head;
    while(temp != NULL && n--) temp = temp->next;
    
    if(temp == NULL) return NULL;
    
    while(temp){
        temp = temp->next;
        head = head->next;
    }
    return head;
}

- HauntedGhost March 05, 2013 | Flag Reply

{{{ //if list is having odd no. of nodes then code is: n* lastnode(n* hptr) { n * slow,*fast; slow=fast=hptr; while(fast->next!=NULL) { slow=slow->next; fast=fast->next->fast; } return fast; } //if list is having even no. of nodes then code is: n* lastnode(n* hptr) { n * slow,*fast; slow=fast=hptr; while(fast->next->next!=NULL) { slow=slow->next; fast=fast->next->fast; } return fast->next; } //this is O(n) solution with only one traversal using two pointer that are moving at different speed - Vaibhav March 11, 2013 | Flag Reply

n* lastnode(n* hptr)
{
	n * slow,*fast;
	slow=fast=hptr;
while(fast->next->next!=NULL)
	{
	slow=slow->next;
	fast=fast->next->fast;
	}
	return fast->next;
}
//for even no. of nodes in the list

- Vaibhav March 11, 2013 | Flag Reply

//if list is having odd no. of nodes then code is: n* lastnode(n* hptr) { n * slow,*fast; slow=fast=hptr; while(fast->next!=NULL) { slow=slow->next; fast=fast->next->fast; } return fast;

- Vaibhav March 11, 2013 | Flag Reply

#include <iostream>
#include <stdlib.h>
#include "List.h"
#include "Node.h"

using namespace std;

int main()
{
    int k = 0;
    int input = 0;
    int element = 0;
    int listSize = rand() % 80;
    List myList;
    cout << endl;
    for(int i = 0; i < listSize; i++){
        input = rand() % 80;
        myList.addNode(input);
    }
    cout << "To find the kth last element in the list, type the value of k: ";
    cin >> k;
    Node *ptr1 = myList.head;
    int counter = 1;
    while(counter != k){
        ptr1 = ptr1->getNext();
        counter++;
    }
    Node *ptr2 = myList.head;
    while(ptr1->getNext() != NULL){
        ptr1 = ptr1->getNext();
        ptr2 = ptr2->getNext();
    }
    element = ptr2->getData();

    cout << "The " << k << "th last element in the list: ";
    myList.printList();
    cout << "is " << element;
}

- Anonymous August 28, 2013 | Flag Reply

class Node {

                int data;
                Node next;

                public Node(int data) {
                        this.data = data;
                        this.next = null;
                }
        }
        
	// Time Complexity O(n)
        Node getElement(Node head, int n) {
                
                Node first = head, second = head;
                
                int count = 0;
                while(null != first && count < n) {
                        first = first.next;
                        count++;
                }
                
                if(count != n) {
                        return first;
                }
                
                while(null != first) {
                        first = first.next;
                        second = second.next;
                }
                
                return second;
        }

- Kapil July 13, 2017 | Flag Reply