This post has already been read 55 times!

Problem

Write a function kth_to_last_node() that takes an integer kand the head_node of a singly-linked list, and returns the  k-th to last node in the list.

Linked Lists

In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.

Solution

Find the K-th to last node in to the LinkedList with Python
# Write a function kth_to_last_node() that takes
# an integer kkk and the head_node of a singly-linked list,
# and returns the kkkth to last node in the list.

# Returns the node with value "Devil's Food" (the 2nd to last node)
# kth_to_last_node(2, a)


class LinkedListNode:

    def __init__(self, value):
        self.value = value
        self.next  = None

    def displayNodeValue(self):
        print(self.value)


def kth_to_last_node(k, head):
    curr = head
    node_list = []

    while curr:
        node_list.append(curr)
        curr = curr.next

    if len(node_list) < k:
        raise IndexError('Invalid index')

    return node_list[len(node_list) - k]


a = LinkedListNode("Angel Food")
b = LinkedListNode("Bundt")
c = LinkedListNode("Cheese")
d = LinkedListNode("Devil's Food")
e = LinkedListNode("Eccles")

a.next = b
b.next = c
c.next = d
d.next = e

assert kth_to_last_node(2, a).value == "Devil's Food"
kth_to_last_node(2, a).displayNodeValue()
Find k-th to the last node in to the LinkedList with C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GetKthNode
{
    /// <summary>
    /// You have a linked list ↴ and want to find the kkth to last node.
    /// Write a function kth_to_last_node() that takes an integer kk and the head_node of a singly linked list, and returns the kkth to last node in the list.
    /// a = Node("Angel Food")
    /// b = Node("Bundt")
    /// c = Node("Cheese")
    /// d = Node("Devil's Food")
    /// e = Node("Eccles")
    /// 
    /// a.next = b
    /// b.next = c
    /// c.next = d
    /// d.next = e
    /// 
    /// kth_to_last_node(2, a)
    /// # returns the node with value "Devil's Food" (the 2nd to last node)
    /// </summary>
    public class GetKthNode
    {
        static LinkedList<Node> _list = new LinkedList<Node>();
        public static void Run()
        {
            var a = new Node("Angel Food");
            _list.AddFirst(a);
            var b = new Node("Bundt");
            _list.AddLast(b);
            var c = new Node("Cheese");
            _list.AddLast(c);
            var d = new Node("Devil's Food");
            _list.AddLast(d);
            var e = new Node("Eccles");
            _list.AddLast(e);
            
            
            kth_to_last_node(2, a);//returns the node with value "Devil's Food" (the 2nd to last node)
        }

        private static void kth_to_last_node(int p, object a)
        {
            var lastCount = _list.Count();
            Node result = _list.ElementAt(lastCount - p);
            var value = result.Value;
            Console.WriteLine(value);
        }

        
    }

    internal class Node
    {
        public string Value { get; private set; }
        public Node(string value)
        {
            Value = value;
        }


        
    }
}

Leave a Reply

Post Navigation