Sunday, February 25, 2007

Nth Element from the last in a Linked List

Another advanced algorithm is to find the Nth Element from the LAST with the optimal performance.
Here is the implementation


using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithms
{
public class LinkedList
{
private Node head;

public LinkedList()
{
head = null;
}

public int FindNthElementFromLast(int m)
{
int n = m - 1;
int returnValue = -1;
if (n >= 0)
{
Node nthElement = head;
Node currentElement = head;
for (int i =0;i less than n;i++)
{
if (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
}
else
{
returnValue = -1;
return returnValue;
}
}

if (returnValue != -1)
{
while (currentElement.NextNode != null)
{
currentElement = currentElement.NextNode;
nthElement = nthElement.NextNode;
}
returnValue = nthElement.DataValue;
}
}
return returnValue;

}

}
public class Node
{
private int dataValue;
private Node nextNode = null;

public Node(int data)
{
dataValue = data;
}
public Node NextNode
{
get
{
return nextNode;
}
set
{
nextNode = value;
}
}
public int DataValue
{
get
{
return dataValue;
}
set
{
dataValue = value;
}
}

}
}

No comments: