How to find the middle element in linked list [clo

问题:

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed last month.

I need a detailed algorithm , in c# about how to find the middle element in linked List. I had checked google and all are talking about the two pointers which moves in parallel over the list . but actually , i couldn't find a detailed solution for the algorithm . and how these two pointers should be implemented .

i need the best solution regarding the performance .

回答1:

This is pretty much what juharr suggested you in the comment for singly-linked list.

GetMiddle starts at head of the list, rightPointer looks two elements ahead, leftPointer looks at the next element (both pointers move in the same direction). In the end, when there are no more elements to examine, leftPointer is the middle node of the list.

In the code below Node is a singly-linked list node, and List just adds elements to the list and exposes its head.

public T GetMiddle<T>(List<T> list)
{
    Node<T> leftPointer = list.Head;
    Node<T> rightPointer = list.Head;

    while (rightPointer != null && rightPointer.Next != null)
    {
        rightPointer = rightPointer.Next.Next;
        leftPointer = leftPointer.Next;
    }

    return leftPointer.Item;
}

public class List<T>
{
    public Node<T> Head { get; private set; }
    private Node<T> Last;

    public void Add(T value)
    {
        Node<T> oldLast = Last;
        Last = new Node<T>(value);

        if (Head == null)
        {
            Head = Last;
        }
        else
        {
            oldLast.Next = Last;
        }
    }
}

public class Node<T>
{
    public T Item { get; private set; }
    public Node<T> Next { get; set; }

    public Node(T item)
    {
        Item = item;
    }
}

In case of even number of elements, like [1, 9]

var list = new List<int>();
foreach (var number in  Enumerable.Range(1, 9))
{
    list.Add(number);
}

Console.WriteLine(GetMiddle(list));

the middle element is 5.

However, in case of even number of elements, line [1, 10], algorithm will produce 6. That is because when right is at 9, it's next is not null but 10. So when we finish this iteration, right is pointing to null and left is pointing at 6 (which we return as middle).

right: 1 -> 3 -> 5 -> 7 -> 9 -> null | end
left:  1 -> 2 -> 3 -> 4 -> 5 -> 6    | end

This means that in even case, you need to decide which element to take as middle - 5 or 6. If you want 5, you will need an extra condition in the loop:

rightPointer = rightPointer.Next.Next;        
if (rightPointer != null)
{
    leftPointer = leftPointer.Next;
}

回答2:

The best solution to finding the middle element with respect to performance is to just compute it:

var mid = list[list.Length/2];

This returns the element after the middle when list.Length is even.

If you want to return the element before the middle when list.Length is even, you can reduce and truncate:

var mid = list[(int)((list.Length-0.5)/2)];

回答3:

A Java solution for the above will be:

public ListNode middleNode(ListNode head) {
    if(head == null || head.next == null) { return head; }
    ListNode slow = head;
    ListNode fast = head;

    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

A Node here is:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}