Linked List te Ortadaki Elmanı Bulma

 Uzun zamandır blog yazmıyordum, geçen bir mülakat sırasında sorulan soruya karşılık bu yazı veya kod parçacığını yazmak istedim. Linked List Nedir başlıklı yazımı 2016 yılında yazmışım. Dolayısıyla çok fazla tanıma vs girmeyeceğim.

public class Node
{
    public int Data { get; set; }
    public Node Next { get; set; }

    Node(int data)
    {
        Data = data;
        Next = null;
    }
}
 
public class LinkedList
{
    Node head;
 
    public void Push(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = head;
        head = newNode;
    }
}
 

 Bir yaklaşım iki tane nesne tanımlayıp, birbirleri ile kısaca yarıştırmak, hızlı olan 2 şer Node ilerlerken yavaş olan birer birer ilerleyecek. Hızlı olan sona geldiğinde , yavaş olan listenin ortasında olacaktır.

public int FindElementAtMiddle()
{
    Node slowPtr = head;
    Node fastPtr = head;

    if (head != null)
    {
        while (fastPtr != null && fastPtr.Next != null)
        {
            fastPtr = fastPtr.Next.Next;
            slowPtr = slowPtr.Next;
        }
    }
    return slowPtr.Data;
}
 
Diğer bir yaklaşım ise, Length diye bir property belirleyip bunu internal olarak her yeni node eklendiğinde arttırmak ve methodumuzun içerisinde listemizin uzunluğunun yarısına kadar dolaşmak olacaktır.
 
public class LinkedList
{
    Node head;
    public int Length { get; private set; }

    public void Push(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = head;
        head = newNode;
               Length += 1;
    }
}
 
public int FindElementAtMiddleWithLength()
{

    Node node = head;
    int index = Length / 2;
    int increment = 0;

    if (head != null)
    {
        while (increment < index)
        {
            node = node.Next;
            increment++;
        }
    }
    return node.Data;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.