Solved

# finding element within singly linked list

Posted on 2013-07-01
1,003 Views
I am working on a question and need some help getting this going.

Write a function that would return the 5th element from the end in a singly linked list of integers, in one pass, and then provide a set of test cases against that function. Assume the list size cannot be known without traversing the list.

My assumption:
I will need a class for the code...and then not sure about the test cases....unless unit tests would be the same thing..if so then another class.

I know I want the 5th element from end.

I do not know the end.

I start a count of some sort that looks ahead in the list until it finds the end...and somehow the other count is looking back to the 5th element...not sure how that works ...but sord of can picture this.

Then I am not sure what all you would test...I guess maybe you would test that there is an a value in the list, that the value is hte 5th element, perhaps that there are even 5 elements...not sure what else to test for here.....

0
Question by:Robb Hill
• 7
• 4

LVL 44

Expert Comment

Is this list a standard collection (List) or one you have coded yourself ?

There is a LastIndexOf function - is that what you require ?
0

LVL 11

Author Comment

pseudocode would be something like this

Have two pointers p1 and p2 point to head of the list.
Now in a while loop keep advancing p1 and p2.
When p2 hits the end of the list p1 will be at the fifth element

Here is some robust code...that needs to be tweeked...or potentially rewritten to up to date standards....please advise
`````` static class Program
{
private static int index = 0;
private static ListNode fifthNode = null;
static int totalNode = 0;
static void Main()
{
ListNode node7 = new ListNode(7, null);
ListNode node6 = new ListNode(6, node7);
ListNode node5 = new ListNode(5, node6);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode root = new ListNode(1, node2);

GetFifthNode(root);//The result;
}

private static void CountTotalNode(ListNode curNode)
{
if (curNode.NextNode == null)
{
return;
}
else
{
totalNode += 1;
CountTotalNode(curNode.NextNode);
}
}
private static void GetFifthNode(ListNode curNode)
{
if (index == totalNode-5)
{
fifthNode = curNode.NextNode;
return;
}
else
{
index += 1;
GetFifthNode(curNode.NextNode);
}
}
}

public class ListNode
{
int _nodeValue;
ListNode _nextNode;

public ListNode()
{
}
public ListNode(int nodeValue, ListNode nextNode)
{
this._nodeValue = nodeValue;
this._nextNode = nextNode;
}
public int NodeValue
{
get
{
return this._nodeValue;
}
set
{
this._nodeValue = value;
}
}

public ListNode NextNode
{
get
{
return this._nextNode;
}
set
{
this._nextNode = value;
}
}

}
``````
0

LVL 62

Assisted Solution

Fernando Soto earned 200 total points
Hi robbhill;

Something like this should work. I would not use a recursive function for this because depending on how many objects you having in the list it could cause a stack overflow.

``````private static void GetFifthNode(ListNode curNode)
{
ListNode n1 = null;   // Will point to the 5th node from the end
ListNode n2 = null;   // Will point to the end node
int nodeCount = 1;    // Make sure that there are at least 5 nodes otherwise can't get 5th node from the end

// Make n2 to be the 5 th node from the begining
for(int i = 1; i <= 5; i++ )
{
if (n2 == null)
{
n2 = curNode;
continue;
}
if( n2.NextNode != null )
{
n2 = n2.NextNode;
nodeCount++;
continue;
}
break;
}

// Check to see if we have 5 or more nodes if not exit
if( nodeCount < 5 )
{
Console.WriteLine("Not enough nodes to get 5th from the end.");
return;
}

// If n2 next node is null assign curNode to n1 because at this point we have 5 nodes
// and curNode would be 5 nodes from the end
if (n2.NextNode == null) n1 = curNode;

// Increment both pointer at the same time until n2.NextNode is null
while( n2.NextNode != null )
{
n1 = n1 == null ? curNode : n1.NextNode;
n2 = n2.NextNode;
}

Console.WriteLine("The 5th node from the end has a value of {0}", n1.NodeValue);

}
``````
0

LVL 11

Author Comment

ok....your helping me alot here.....this node stuff is not something I have done much of except with xml a while back ...this seems different...so if I want to do some test cases...how would you go about that........in the meantime I am trying to string something up to test this...

do you have an easy way to test..when this is just in a class.  I am using vs 2013.
0

LVL 62

Expert Comment

Hi;

First I want to say that Microsoft does have a class which implements a doubly linked list which is much better then implementing your own.

To answer your question this function should be a part of your ListNode class. Also I would make it more genetic so that you can ask for any node that is X nodes from the end. To test create a LinkedList and then X node from the end and make sure that the results is what you are asking for.

.
0

LVL 11

Author Comment

I need to stay in the singly linked list.

ok so would you just add this method into my code...as is?

...im still not sure on the test...as in ...I am looking at visual studio....I have a solution, with a project ..with this one class in it....

where would I put this test..so I can compile it and see some results.......I know how to use nunit..but this is a test case...not sure how to implement that....or rather picture in my head
0

LVL 62

Expert Comment

To your question, "ok so would you just add this method into my code...as is?", well if you only need to find the 5th node from the end, always, then yes, otherwise make it more generic by changing everywhere it checks for 5 to check for the distance you want to find.

I have not run NUnit test a whole lot and it's been a while, so I would not be of much help there. What I would do is in the main function of the console application I would create an instance of the ListNode LinkedList with different sizes and run the code to find the node from the end of the list, currently in your code called GetFifthNode(...). By the way it may be better to have that function to return the node you are looking for then to return void.

.
0

LVL 11

Author Comment

Here is the code...but I still cannot run it....the encapsulation seems like it needs to be refined.....how would you wire this up to run.

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

{
static class Program
{
private static int index = 0;
private static ListNode fifthNode = null;
static int totalNode = 0;
static void Main()
{
ListNode node7 = new ListNode(7, null);
ListNode node6 = new ListNode(6, node7);
ListNode node5 = new ListNode(5, node6);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode root = new ListNode(1, node2);

GetFifthNode(root);//The result;
}

private static void CountTotalNode(ListNode curNode)
{
if (curNode.NextNode == null)
{
return;
}
else
{
totalNode += 1;
CountTotalNode(curNode.NextNode);
}
}
private static void GetFifthNode(ListNode curNode)
{
if (index == totalNode-5)
{
fifthNode = curNode.NextNode;
return;
}
else
{
index += 1;
GetFifthNode(curNode.NextNode);
}
}
}

public class ListNode
{
int _nodeValue;
ListNode _nextNode;

public ListNode()
{
}
public ListNode(int nodeValue, ListNode nextNode)
{
this._nodeValue = nodeValue;
this._nextNode = nextNode;
}
public int NodeValue
{
get
{
return this._nodeValue;
}
set
{
this._nodeValue = value;
}
}

public ListNode NextNode
{
get
{
return this._nextNode;
}
set
{
this._nextNode = value;
}
}

private static void GetFifthNode(ListNode curNode)
{
ListNode n1 = null;   // Will point to the 5th node from the end
ListNode n2 = null;   // Will point to the end node
int nodeCount = 1;    // Make sure that there are at least 5 nodes otherwise can't get 5th node from the end

// Make n2 to be the 5 th node from the begining
for (int i = 1; i <= 5; i++)
{
if (n2 == null)
{
n2 = curNode;
continue;
}
if (n2.NextNode != null)
{
n2 = n2.NextNode;
nodeCount++;
continue;
}
break;
}

// Check to see if we have 5 or more nodes if not exit
if (nodeCount < 5)
{
Console.WriteLine("Not enough nodes to get 5th from the end.");
return;
}

// If n2 next node is null assign curNode to n1 because at this point we have 5 nodes
// and curNode would be 5 nodes from the end
if (n2.NextNode == null) n1 = curNode;

// Increment both pointer at the same time until n2.NextNode is null
while (n2.NextNode != null)
{
n1 = n1 == null ? curNode : n1.NextNode;
n2 = n2.NextNode;
}

Console.WriteLine("The 5th node from the end has a value of {0}", n1.NodeValue);

}

}

}
``````
0

LVL 11

Author Comment

This code now has two get fifth node methods...i am not sure what to do with this......
0

LVL 11

Accepted Solution

Robb Hill earned 0 total points
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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

static void Main(string[] args)
{
int[] arr = new int[] { 0, 1, 2, 3, 4, 5, 6 };
int lastLocation = 0;

while (true)
{
try
{
Console.Out.WriteLine(arr[lastLocation]);

lastLocation = lastLocation + 5;
}
catch (Exception e)
{
Console.Out.WriteLine(e.Message);
break;
}
}

lastLocation--;

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

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

LVL 62

Expert Comment

Hi robbhill;

From you last post I can see that this seems to be a class assignment. It seems that the solution I posted was not worth full credit.

By the way when I stated that you should place the function GetFifthNode(...) in the ListNode class I did not mean to keep the other version in the code. Also when you moved it to the ListNode class you need to remove the static keyword from the functions signature.

One more thing your main function never seems to create an instance of the LinkedList and never finds the 5th node from the end.

.
0

LVL 11

Author Closing Comment

Thanks for the assistance Fernando..I gave you credit for helping..I posted the entire solution.
0

## Featured Post

### Suggested Solutions

Recently while returning home from work my wife (another .NET developer) was murmuring something. On further poking she said that she has been assigned a task where she has to serialize and deserialize objects and she is afraid of serialization. Wha…
This article describes relatively difficult and non-obvious issues that are likely to arise when creating COM class in Visual Studio and deploying it by professional MSI-authoring tools. It is assumed that the reader is already familiar with the cla…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
This video discusses moving either the default database or any database to a new volume.