// Question : Find Kth element from the last element in a singly linked list. 

// Solution : Use a recursive approach to find the Kth to the last element. In recursive approach we reach the end of the list first and then work our way up as the counter is incremented in each step. 

// When the counter equals the number K, we print out the value.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using SLL;

​

public class Program

{

    public static void Main()

    {

        List list = new List();

        // Add a few elements to the list.

        list.Add(5);

        list.Add(8);

        list.Add(9);

        list.Add(1);

        list.Add(2);

        list.Add(3);

        int k = 0;

        Console.WriteLine();

        Console.WriteLine("Find Kth element from the last element in the list. Enter the value of K:");

        k = Convert.ToInt32(Console.ReadLine());

        list.FindKthElement(list.Head, k);

        Console.WriteLine("---------------------");

    }

}

​

namespace SLL

{

    /// <summary>

                                            /// A simple basic implementation of singly linked list in C#. The List class implements Add, Find and Delete funcationality without using built-in .NET classes.

                                            /// </summary> 

    internal class List

    {

        /// <summary>

                                                                                        /// Node class

                                                                                        /// </summary>

        internal class Node

        {

            private int data;

            private Node next = null;

            /// <summary>

                                                                                                                                    /// Pointer to next node.

                                                                                                                                    /// </summary>

            internal Node Next

            {

                get

                {

                    return next;

                }

​

                set

                {

                    next = value;

                }

            }

​

            /// <summary>

                                                                                                                                    /// Data stored in the node.

                                                                                                                                    /// </summary>

            internal int Data

            {

                get

                {

                    return data;

                }

​

                set

                {

                    data = value;

                }

            }

​

            /// <summary>

                                                                                                                                    /// Constructor

                                                                                                                                    /// </summary>

                                                                                                                                    /// <param name = "d"></param>

            internal Node(int d)

            {

                data = d;

            }

        }

​

        private int _length;

        private Node _head;

        /// <summary>

                                                                                        /// Head of the list

                                                                                        /// </summary>

        internal Node Head

        {

            get

            {

                return _head;

            }

        }

​

        /// <summary>

                                                                                        /// Length of the list

                                                                                        /// </summary>

        internal int Length

        {

            get

            {

                return _length;

            }

        }

​

        /// <summary>

                                                                                        /// Default Constructor

                                                                                        /// </summary>

        internal List()

        {

            _length = 0;

            _head = null;

        }

​

        /// <summary>

                                                                                        /// Display all nodes.

                                                                                        /// </summary>

        internal void ShowNodes()

        {

            // Print all nodes till the end of the list.

            Node current = _head;

            if (current == null)

            {

                Console.WriteLine("No more nodes to display.");

                Console.WriteLine();

            }

            else

            {

                ShowLength();

                while (current != null)

                {

                    Console.WriteLine("Node : " + current.Data);

                    current = current.Next;

                }

​

                Console.WriteLine();

            }

        }

​

        /// <summary>

                                                                                        /// Show length of the list.

                                                                                        /// </summary>

        internal void ShowLength()

        {

            string numString = "numbers";

            if (_length == 1)

            {

                numString = "number";

            }

​

            Console.WriteLine(String.Format("List has [{0}] {1}.", _length.ToString(), numString));

        }

​

        /// <summary>

                                                                                        /// To insert a new Node at the end of the list.

                                                                                        /// </summary>

                                                                                        /// <param name = "d"></param>

        internal void Add(int d)

        {

            Console.WriteLine();

            Console.WriteLine(String.Format("Add node [{0}].", d.ToString()));

            // Create a new Node instance with given data;

            Node newNode = new Node(d);

            Node current = _head;

            if (_head == null)

            {

                _head = newNode;

            }

            else

            {

                // Traverse till the end of the list....

                while (current.Next != null)

                {

                    current = current.Next;

                }

​

                // Add new node as the next node to the last node.

                current.Next = newNode;

            }

​

            _length++;

            ShowNodes();

        }

​

        private int i;

        internal void FindKthElement(Node head, int k)

        {

            if (head == null)

            {

                return;

            }

​

            FindKthElement(head.Next, k);

            if (++i == k)

            {

                Console.WriteLine(String.Format("Element at index [{0}] from the last element in the list is [{1}].", k.ToString(), head.Data.ToString()));

            }

        }

    }

}