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.

CodingInterviewPractice_2013_01_02.cs

/****************************************************************
    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);
        }
    }
}