Find the kth to the last element on a single linked list


  • 0
    O

    Find the kth to the last element on a single linked list

    i.e. if the list is { 1, 4, 6, 3, 6, 7 }

    when k = 2, kth to last is 6.

    when k = 1, kth to last is 7.

    when k = 10000, kth is null, since there aren't that many items on the list

    public LinkedListImpNode FindKthToLast(int k)
    {
        LinkedListImpNode p = Head;
        LinkedListImpNode kNode = Head;
        //first advance k
        int i = 0;
        for (; i < k && p != null; i++)
        {
            p = p.Next;
        }
        if (p == null && i < k)
        {
            // the list is too small, we reached the end of the list
            // and we did not find k elements, fail here.
            return null;
        }
    
        //move the pointer to the end, sk moves with it
        while (p != null)
        {
            p = p.Next;
            kNode = kNode.Next;
        }
        return kNode;
    }
    

    Here is a testcase

    [TestMethod]
    public void FindKthTests()
    {
        // build the list  {1, 4, 6, 3, 6, 7}
        LinkedListImp list = new LinkedListImp();
        list.AddToEnd(1);
        list.AddToEnd(4);
        list.AddToEnd(6);
        list.AddToEnd(3);
        list.AddToEnd(6);
        list.AddToEnd(7);
    
        Assert.AreEqual(1, list.FindKthToLast(6).Value);
        Assert.AreEqual(3, list.FindKthToLast(3).Value);
        Assert.AreEqual(6, list.FindKthToLast(2).Value);
        Assert.AreEqual(7, list.FindKthToLast(1).Value);
        Assert.IsNull(list.FindKthToLast(7));
    }

  • -1
    D
     private static int FindKth(ListNode head, int k)
            {
                //null check
                if (head == null || k < 1)
                    return -1;
    
                int i = 1;
                ListNode val = head;
                while (head != null)
                {
                    // not enough nodes
                    if (head.next == null && i < k)
                        return -1;
                    else
                    {
                        if (i == k && head.next == null)
                        {
                            return val.val;
                        }
                        else
                        {
                            if (i == k)
                                val = val.next;
                            else
                                i++;
                        }
                        head = head.next;
    
                    }
                }
    
                return -1;
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.