Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Implement a simple singly-linked list data structure. Write a function to remove a list's 3rd from last element. (Challenge: can you do it in a single list traversal?) Write a function to remove all duplicates from a linked list. (Challenge: can you do it without storing any extra data?) Write a function to detect a loop in a linked list.
/****************************************************************
Adam Lum
01/05/2013
Coding for Interviews on Linked Lists
http://codingforinterviews.com
Implement a simple singly-linked list data structure.
Write a function to remove a list's 3rd from last element.
(Challenge: can you do it in a single list traversal?)
Write a function to remove all duplicates from a linked list.
(Challenge: can you do it without storing any extra data?)
Write a function to detect a loop in a linked list.
*******************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace CodingInterviewPractice_2013_01_02
{
class Node
{
public int value = 0;
public Node next = null;
}
class Program
{
static void Main(string[] args)
{
Node n1 = new Node(), n2 = new Node(), n3 = new Node(), n4 = new Node(), n5 = new Node();
n1.value = 2;
n2.value = 4;
n3.value = 6;
n3.value = 8;
n4.value = 10;
n5.value = 12;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
}
static void removeThirdNode(Node _startingNode)
{
Node currentNode = _startingNode;
int nodeNum = 1;
while (nodeNum < 3 && currentNode != null)
{
if (nodeNum == 2)
{
if (currentNode.next != null)
{
currentNode.next = currentNode.next.next;
}
}
currentNode = currentNode.next;
nodeNum++;
}
}
static void removeDuplicateNodes(Node _startingNode)
{
Node baseNode = _startingNode;
Node currentNode = _startingNode;
if (currentNode != null)
{
while (currentNode.next != null)
{
if (baseNode.value == currentNode.next.value)
{
currentNode.next = currentNode.next.next;
}
currentNode = currentNode.next;
}
removeDuplicateNodes(baseNode.next);
}
}
static bool detectLoop(Node _startingNode)
{
Node oneStepNode = _startingNode.next;
Node twoStepNode = _startingNode.next.next;
while (oneStepNode != null && twoStepNode != null)
{
if (oneStepNode == twoStepNode)
{
return true;
}
if (oneStepNode.next == null)
{
return false;
}
else
{
oneStepNode = oneStepNode.next;
}
if (twoStepNode.next == null)
{
return false;
}
else
{
twoStepNode = twoStepNode.next.next;
}
}
return false;
}
static void outputList(Node _startingNode)
{
Node currentNode = _startingNode;
int count = 0;
do
{
if (count > 0)
{
Console.Write(", ");
}
Console.Write(currentNode.value);
currentNode = currentNode.next;
count++;
} while (currentNode != null);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment