CareerCup

Use two pointers both pointing to the head of the linked list. Move one of the pointers k ahead. Now move both of the pointers one node ahead at a time. When the first one reaches the end the second one would be k nodes behind it.

void printKthFromLast(struct node *head, int k){
  struct node *main_ptr = head;
  struct node *ref_ptr = head;
 
  int count = 0;
  if(head != NULL){
     while( count < k ){
        if(ref_ptr == NULL){
           printf("There are fewer than %d nodes in the list", k);
           return;
        }
        ref_ptr = ref_ptr->next;
        count++;
     }
 
     while(ref_ptr != NULL){
        main_ptr = main_ptr->next;
        ref_ptr  = ref_ptr->next;
     }
     printf("%d the node from the end is %d", 
              k, main_ptr->data);
  }
}

Just have two references/pointers. Ref1 and Ref2

for(i 0->k-1)
	move Ref2 only

Now move both pointers together. As soon as Ref2 will hit NULL, you will get Ref1 as desired.

#include<iostream>
#include<list>
int findkthreverseelement(const std::list<int>& elements, int k) {
        std::list<int>::const_iterator front = elements.begin();
        std::list<int>::const_iterator back = front;

        for (int i = 1; i <= k; i++) ++front;

        while (front != elements.end()) {
                ++front;
                ++back;
        }
        return *back;
}

int main() {

        std::list<int> elements;
        int input=0;
        int k;
        std::cout << "Enter k\n";
        std::cin >> k;
        std::cout << "Enter elements\n";
        while (std::cin >> input) {
                elements.push_back(input);
        }

        for(std::list<int>::iterator it = elements.begin(); it != elements.end(); ++it) {
                std::cout << *it << " ";
        }


        int result = findkthreverseelement(elements, k);
        std::cout << "answer is " << result << "\n";

        return 0;
}

I think your missing an important fact that could partition to n/2, just by adding a counter to the list you will know where to start if from head or tail...

With Size given problem will be too simple to solve so i will try solving without the Size
1.Have two pointers both of them pointing to head at first assume P1 and P2
2.move p2 to k times in the list(assuming the question is kth to last )

(for int i=0;i<k-1;i++){
p2=p2.next;
}

4.now P2 will be k node in to the list and P1 still pointing to the head
5.now move P1 and p2 on the same speed iterating over the list

while p2.next !=null// that means list's end
{
p1=p1.next;
p2=p2.next;
}
return p1

If size is not a constraint, then for finding length traverse through the list and at the same time copy the data into a array. Now you can directly get the kth data in single shot. total time complexity is O(N) for getting length, and O(1) for getting kth element.

Node find() {
		Node next = this.head();
		Node prev =this.head();
		for (int i = 0 ; i < k ; i++) {
			next = next.nextNode();
			if (next == null)
				return null;
		}
		while( next!= null) {
			next = next.nextNode();
			prev = prev.nextNoce();
		}
		return prev;
	}

take a pointer say k = head
1. increment it k times,
2. now increment both head and k till k reaches last,
the element head points to is the kth from last :)

An answer below this question uses two pointers which has the distance k. Move them simultaneously. When the first pointer catch the last one, the second pointer reach to kth element from the tail.
There is a trick, this method have to move 2 * length in the whole. So there is an more efficient method.

Just as the answer mentioned above, we have:
first pointer
second pointer

second pointer points to the head, while first pointer points to kth element in the linked list

You can simply move first pointer k(sometimes less than k times, because maybe list has not enough elements to traverse) times every single loop, remember the times to T, after every k times movement, check whether first pointer reach the end. If not, let second pointer point to the position which first pointer points when this loop begins, and go on. If so, move second pointer T times and this is the kth element from the tail in the linked list.


Now i just use k to be the number of moves for first pointer every single loop. When k is much smaller than the linked list length, this method seems not more efficient than traditional one. So how to makes this method most efficient? With my glance, I think we could choose the number of moves every single loop dynamically. The best number is related to k and length of linked list.

class Node(object):
    def __init__(self, value, node):
        self.value = value
        self.node = node

root = Node(0,None)
previousNode = root
for i in range(1, 50):
    node = Node(i, None)
    previousNode.node = node
    previousNode = node

node = root
for i in range(50):
    print node.value
    node = node.node

def kthElementFromTail(k):
    p = root
    kthFromTail = 0
    q = p;
    for i in range(k):
        if(q.node != None):
            q = q.node
        else:
            print "k is out of range of linkedList"
            return
    while q.node != None:
        temp = q
        position = 0
        for i in range(0,k):
            if(q.node != None):
                position += 1
                q = q.node
            else:
                break
        if(position < k):
            for i in range(position):
                p = p.node
            return p
        else:
            kthFromTail += position
            p = temp
    return None

k = kthElementFromTail(3)
print k.value

static Node GetTheKthFromTailNode(Node head, int k)
		{
			Node runner = head;
			while (--k != 0 && runner != null)
			{
				runner = runner.Next;
			}

			if (runner == null) return null;

			Node result = head;
			while (runner.Next != null)
			{
				runner = runner.Next;
				result = result.Next;
			}

			return result;
		}

function item findElemFromTail(LinkedList list, int k) {
   item* p = list->head;   
   item* elem = NULL;
   int k = ;
   int i = 0;
   while(p!=null) {
        if(i == k) {
           elem = p;
        }      
        if (item!=null) item = item->next;
        p = p->next;
        i++;
   }

   return elem;
}

This is O(N) and we are only scanning the linked list once.

xx: temp=head;
for(i=0;i<k;i++)
{
temp->temp->next;
}
if(temp->next==NULL)
{
return(head->no);
}
else
{
head=head->next;
goto xx;
}

public Node<E> findKthElementFromEnd(int k) {
		if (k < 0 || this.size - k < 0) {
			System.out.println("Enter Correct value of K");
			return null;
		}
		if (head == null || head.next == null)
			return head;

		Node<E> fast = head;
		Node<E> slow = head;
		int i = 0;
		while (i < k) {
			fast = fast.next;
			i++;
		}

		while (fast != null) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

In java
--same as C++ program above. Please include the check for K > size of the list.
1.) move the fast pointer to kth position
2.) move the fast and slow pointers by one
3.) exit when fast reached the end
4.) print the value of the slow pointer

public void findKthElement(int k)
       {
      	if( head == null ){  
      		return;
      	}
        //add condition to handle k >= length of list

      	Node<AnyType> fast = head;
      	Node<AnyType> slow = head;
      	while(k > 0){
      		fast = fast.next;
      		k--;
      	}
      	while(fast != null){
      		fast = fast.next; 
      		slow = slow.next;	
      	}
      	
      	System.out.println("kth element value is: " + slow.data );
       }

public class KthElementFromTail {
	public static void main(String args[]){
		SLLImpl list = new SLLImpl();
		list.addToTail(1);
		list.addToTail(2);
		list.addToTail(3);
		list.addToTail(4);
		list.addToTail(5);
		list.addToTail(6);
		int element = getKthElementFromTail(2, list);
		System.out.println(element);
	}

	private static int getKthElementFromTail(int index, SLLImpl list) {
		int position = 1;
		SLLNode node = null;
		for(node = list.head; position != list.size - index; node=node.next){
			position++;			
		}
		return node.data;		
	}
}

public class KthElementFromTail {
	public static void main(String args[]){
		SLLImpl list = new SLLImpl();
		list.addToTail(1);
		list.addToTail(2);
		list.addToTail(3);
		list.addToTail(4);
		list.addToTail(5);
		list.addToTail(6);
		int element = getKthElementFromTail(2, list);
		System.out.println(element);
	}

	private static int getKthElementFromTail(int index, SLLImpl list) {
		int position = 1;
		SLLNode node = null;
		for(node = list.head; position != list.size - index; node=node.next){
			position++;			
		}
		return node.data;		
	}
}

Either hold last k seen nodes (time compexity O(n), space O(k)), or traverse the list twice (O(n) / O(1))

If you know the length of the given linked list, just subtract from the length and do one traversal to get it from the "front" of the list:

public static Node getKFromTail(int k) {
		int from_zero = length-k-1;
		Node curr = top;
		for(int i = 0; i<from_zero; i++) {
			curr = curr.next;
		}
		return curr;
	}

In Java

public  E findLastFromList(int seq, LinkedList<E> list){
		int size = list.size();
		if (size < seq) {
			return null;
		}
		return list.get(size - seq );
	}

Can be done in O(n) time. Travel the list in O(n) time. This will give you the length of the list - lets say 'n'.
SUbtract k from the length and 1 in it. (n-k)+1
Once again travel from beginning and n-k+1 is the kth element from the tail.

import java.util.Scanner;

public class LinkedInsert {
	static Node[] newNode;
	static int numberOfNode;

	public static void main(String args[]) {
		Node head = null;
		System.out.print("Enter Number of Node:");
		numberOfNode = new Scanner(System.in).nextInt();
		newNode = new Node[numberOfNode];
		for (int i = 0; i < numberOfNode; i++) {
			int d = new Scanner(System.in).nextInt();
			newNode[i] = new Node(d);
			if (i == 0) {
				head = newNode[i];
			}

			else {
				head.nextNode = newNode[i];
				head = newNode[i];
			}

		}


		System.out.print("Enter Find Data:");
		int find = new Scanner(System.in).nextInt();
		getSpecificElementFromTailOfStack(find);
	}

	private static void getSpecificElementFromTailOfStack(int find) {
		// TODO Auto-generated method stub
		int f = numberOfNode - find;
		System.out.print("Data:" + newNode[f].data);
	}

}

convert the linked list into a min-heap and return the kth element

#include<iostream>
using namespace std;
struct node{
int data;
node *next;
};

int my_func(node *new_list,int m)
{
node *bptr;int count=0,count1=0,count2=0;
bptr=new_list;

while((bptr->next)!=NULL)
{
bptr=bptr->next;
count1++;

}
count2=count1-m+1;
bptr=new_list;
while((count2>0))
{
bptr=bptr->next;
count2--;
}

int h=bptr->data;
return h;


}
int main()
{
node *list,*nptr,*tptr;
int item,n,i;
list=NULL;

cout<<"PLEASE.......Type how many nodes that you want ";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"Type your "<<i<<" node item ";
cin>>item;
nptr=new(node);
nptr->data=item;
nptr->next=NULL;
if(list==NULL)
{
list=nptr;
tptr=nptr;
}
else
{
tptr->next=nptr;
tptr=nptr;
}
}
tptr=list;
for(i=1;i<=n;i++)
{
cout<<endl;
cout<<tptr->data<<" ";
tptr=tptr->next;

}
cout<<endl;
cout<<"Enter your node number from the tail in a linked list ";
cin>>item;

int data_new=my_func(list,item);

cout<<" \n\n"<<item<<" element from the tail in a linked list= "<<data_new<<endl<<endl;
return 0;



}

void printKthElementReverse(int nPos)
{
if(pHead == NULL)
{
std::cout<<"No Element Found at "<<nPos<<" position";
return;
}
int count = 0;
stList* pCurr = pHead;
stList* pKthElem = pHead;
stList* pPrev = NULL;
while(count < nPos)
{
pPrev = pKthElem;
if(NULL == pKthElem)
break;
pKthElem = pKthElem->pNList;
count++;
}

if(pPrev == NULL || count < nPos)
{
std::cout<<"No Element Found at "<<nPos<<" position";
return;
}

stList* pCurPrev = NULL;
while(pPrev != NULL)
{
pCurPrev = pCurr;
pPrev = pPrev->pNList;
pCurr = pCurr->pNList;
}

std::cout<<nPos<<" Element from Reverse is "<<pCurPrev->data;
}