Skip to content

Instantly share code, notes, and snippets.

@rodchile
Last active August 29, 2015 14:16
Show Gist options
  • Save rodchile/91a419222b9871b1701d to your computer and use it in GitHub Desktop.
Save rodchile/91a419222b9871b1701d to your computer and use it in GitHub Desktop.
order singly linked list nodes based on value
public class SinglyNode {
public SinglyNode next = null;
public int value;
public SinglyNode(int d)
{
value = d;
}
public static SinglyNode orderNodes(SinglyNode node, int value)
{
SinglyNode tortoise = node;
SinglyNode lessThan = null;
SinglyNode moreThan = null;
while(tortoise != null)
{
if (tortoise.value < value)
{
placeNode(lessThan, tortoise);
}
else
{
placeNode(moreThan, tortoise);
}
tortoise = tortoise.next;
}
mergeLists(lessThan, moreThan);
return lessThan;
}
public static void mergeLists (SinglyNode headListLeft, SinglyNode headListRight)
{
if(headListLeft.next == null)
{
headListLeft.next = headListRight;
return;
}
else
{
mergeLists(headListLeft.next, headListRight);
}
}
public static void placeNode (SinglyNode head, SinglyNode p)
{
if (head == null)
{
head = copyNode(p);
return;
}
if (head.next == null)
{
head.next = copyNode(p);
}
else
{
placeNode(head.next, p);
}
}
public static SinglyNode copyNode(SinglyNode p)
{
return new SinglyNode(p.value);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment