CareerCup

1)Take 2 pointer move one pointer by 5 position ie, the difference between the two pointer is 5.
2)Now traverse through the list till the first pointer reaches the end of the list
3) now the second pointer will be pointing to the 5th element from the last.

Another way is using a queue data structure, which size is 5. Then enqueue the value of the linked list, and dequeue the head when the queue is full, after one pass, the head of the queue is the number you want.

Use One pointer to the list and a queue of size 5:
1) traverse to the 5th node
2) insert the element at the queue
3) if the queue is full, take rear element out and insert the new element at the front
4) repeat it till the pointer reaches null
5) the rear pointer of the queue contains the 5th element from the tail of the list..

Using an size-5 circular buffer:
const int Size = 5;
Node[] buffer = new Node[Size];
int index = 0;
foreach (Node n in linkedList)
{
buffer[index] = n;
index = (index + 1) % Size;
}
return buffer[index];

hey what does one pass here means? does it mean that we can't use recursion?

1) Take two pointers both at the start of linklist.
2) Advance one pointer by 5 positions.
3) then advance both the pointers simultaneously until second pointer becomes null.
4) Return first pointer.

node* fun(node* head)
{
if(head==null)
{cout<<"not enough elements"; return null;}

node*ptr1,*ptr2=head;

for (int i=0;i<5&&ptr2!=null;i++)
ptr2=ptr2->next;

if(ptr2==null) {cout<<not enough elements; return null;}

while (ptr2!=null)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
}

return ptr1;

}


Example: A->B->C->D->E->F->G->*(end)

5th from last: C
after loop1
ptr2=F

after loop2
ptr1=c

One pass means we can traverse the list only once.

We can do this in one pass using a pointer and a queue of length 5
pseudo code

function 5th_from_tail( head )
	s = queue length 5
	s = Null
	ptr = head
	while ptr != Null
		s.push_to_head(ptr)
		ptr = ptr -> next
		
	element = s.pop_from_tail()
	if element == Null
		return "not enough elements"
	else
		return element

list_node * get5thNode()
{
    list_node * temp = NULL;
    list_node * runner = headNode;
    int index = 1;

    while(runner->next != NULL)
    {
        runner = runner->next;
        if(index > 5)
        {
            if(!temp)
                temp = headNode;
            else
                temp = temp->next;
        }
        index++;
    }
    return temp;
}

O(n) solution
General Solution to find nth node from tail

public class FifthNodeFromTailLinkedList {
    private static final int nthNode = 5;
    public static Node getNthNodeFromTail(Node head) {
        if (head == null) {
            return null;
        }

        Node nthTailNode = null;
        int count = 0;
        Node node = head;
        while (node != null) {
            count ++;
            if (count == nthNode) {
                nthTailNode = head;
                break;
            }
            node = node.getNext();
        }

        while (node.getNext() != null) {
            nthTailNode = nthTailNode.getNext();
            node = node.getNext();
        }
        return nthTailNode;
    }

    public static void main(String args[]) {
        Node node = new Node(1);
        node.setNext(new Node(2));
        node.getNext().setNext(new Node(3));
        node.getNext().getNext().setNext(new Node(4));
        node.getNext().getNext().getNext().setNext(new Node(5));
        node.getNext().getNext().getNext().getNext().setNext(new Node(6));

        System.out.println(getNthNodeFromTail(node).getValue());
    }
}

class Node {
    private int value;
    private Node next;

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}

Output:

2

Using implicit Stack :

Lnode* kthFromTail(Lnode* start, int k)
{
   static int count =0;
   if(!start)
        return NULL;

   Lnode* end = NULL;
   end = kthFromTail(start->next, k);
   count++;
   if(count==k) end = start;
   return end;
}

/*
* Write a function that would return the 5th element from the
* tail (or end) of a singly linked list of integers, in one pass,
* and then provide a set of test cases against that function
* (please do not use any list manipulation functions that you
* do not implement yourself).
*/
class App {

public static void main(String[] args) {
int arr[] = new int[] { 0, 1, 2, 3, 4, 5, 6 };

int lastLocation = 0;

while (true) {
try {
System.out.println(arr[lastLocation]);

lastLocation = lastLocation + 5;
} catch (ArrayIndexOutOfBoundsException e) {
//System.out.println("arr Out of index: " + lastLocation);
break;
}
}

lastLocation--;

for (int i = 0; i < 5; i++) {
try {
// This sysout statement ensure that same element is not hit
// twice
System.out.println(arr[lastLocation]);
if(lastLocation < 4) {
System.out.println("Array Length less than 5");
break;
}

// System.out.println("Last element of array: "
// + arr[lastLocation]);
System.out.println("5th Last element of array: "
+ arr[lastLocation - 4]);
break;
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println(lastLocation--);
}
}
}
}

two pointer and one counter
1) one pointer keep moving till the end, everyone move, counter will increase one
2) when counter is >= Nth (e.g 5), the second pointer will starting pointing from head, since then, every since first pointer move, second pointer will also move
3) when first move till the end of list, return second pointer

using System;

namespace ConsoleApplication1
{
    class NTHElementFromTailFromList
    {
        static void Main(string[] args)
        {
            Node node = new Node
            {
                value = "1",
                next = new Node
                {
                    value = "2",
                    next = new Node
                    {
                        value = "3",
                        next = new Node
                        {
                            value = "4",
                            next = new Node
                            {
                                value = "5",
                                next = new Node
                                {
                                    value = "6",
                                    next = new Node
                                    {
                                        value = "7",
                                        next = null
                                    }
                                }
                            }
                        }
                    }
                }
            };

            Node nTh = FindNthElementTail(node, 2);

            Console.WriteLine(nTh);
        }

        static Node FindNthElementTail(Node n, int nth)
        {
            Node nThElement = null;
            Node head = n;
            int count = 0;

            while (n != null)
            {
                count++;

                if (count >= nth)
                {
                    if (nThElement == null)
                    {
                        nThElement = head;
                    }
                    else
                    {
                        nThElement = nThElement.next;
                    }
                }

                n = n.next;
            }

            return nThElement;
        }
    }

    class Node
    {
        public Node next { get; set; }
        public string value { get; set; }

        public override string ToString()
        {
            return this.value;
        }
    }
}

// maintain two pointers fast and slow

ListNode* kthNodeFromEnd(ListNode* head, int k)
{
     if (head == NULL) return NULL; 
     ListNode* fast = head, slow = head;
     while (--k && fast->next != NULL) fast = fast->next;
     if (fast == NULL) return NULL;
     while (fast->next != NULL) {
             fast = fast->next;
             slow = slow->next;
      }
      return slow;
}

Do it with tail recursion. Write a recursive function that, given a node in the list, returns the order of that node from the tail.

{ public static void findpos(LinkedList linkedList,LinkedList.Node head,int n)
      {
      LinkedList.Node temp = head;
      LinkedList.Node pos = head;
      int length=0;
       int i=0;
    
      while (i<n){
    	  
    	  temp=temp.next();
          i++;
      }
        
      while(temp.next() !=null)
      {
        pos=pos.next();
        temp=temp.next();
    	  
      }
        
      
      System.out.println("Element at n th from last = "+ n + "  of LinkedList : " + pos.data());
     
    }

public class NthFromLast {

static class Node {
int value;
Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public String toString() {
return String.valueOf(value);
}
}

int counter = 0;
Node nthNode;


public Node getNthNode(Node first, int n) {
getNthNodeRecursive(first, n);
return nthNode;
}

private void getNthNodeRecursive(Node first, int n) {

if(first == null) {
return;
}

if(first.next != null) {
getNthNodeRecursive(first.next, n);
}

counter++;

if(counter == n) {
nthNode = first;
}

}

public static void main(String [] args) {
Node first = new Node(1,
new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, null))))));

NthFromLast n = new NthFromLast();
System.out.println(n.getNthNode(first, 4));
}

}

This one is using recursion, single pass and O(1) space. Apologies for the duplicate post.

public class NthFromLast {

	static class Node {
		int value;
		Node next;
		public Node(int value, Node next) {
			this.value = value;
			this.next = next;
		}
		public String toString() {
			return String.valueOf(value);
		}
	}
	
	int counter = 0;
	Node nthNode;
	
	
	public Node getNthNode(Node first, int n) {
		getNthNodeRecursive(first, n);
		return nthNode;
	}
	
	private void getNthNodeRecursive(Node first, int n) {
		
		if(first == null) {
			return;
		}
		
		if(first.next != null) {
			getNthNodeRecursive(first.next, n);
		}
		
		counter++;

		if(counter == n) {
			nthNode = first;
		}
		
	}
	
	public static void main(String [] args) {
		  Node first = new Node(1, 
				  new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, null))))));
		  
		  NthFromLast n = new NthFromLast();
		  System.out.println(n.getNthNode(first, 4));
	}
	
}

1. get the size of the linked list say size
2. calculate size-5 = traverseLength
3. From the head pointer traverse linked list by traverseLength and print the element.

whats wrong with using something like
current=first
while(current.next.next.next.next.next!=null)
current=current.next;


where next is the next node.

class Node {
Object data;
Node next;
};

Node 5thToTail(Node head)
{
if (head == null)
{
throw Exception("Error: empty linked list");
}
else
{
Node p1 = head, p2 = head;
int i = 1;
for(; i<5; i++)
{
if (p1.next != null)
{
p1 = p1.next;
}
}

if (i < 5)
{
throw Exception("Error: elements are less than 5 in the linked list");
}

while (p1.next != null)
{
p1 = p1.next;
p2 = p2.next;
}

return p2;
}

}