Как найти средний элемент в списке ссылок без прохождения всего списка.?... и в максимуме вы можете использовать только 2 указателя... как это сделать?.... а также длина списка не указана.
Как найти средний элемент в списке ссылок без прохождения всего списка?
Ответ 1
Я не вижу, как вы могли бы это сделать без прохождения всего списка, если не знаете длину.
Я предполагаю, что ответ хочет, чтобы один указатель проходил по одному элементу за раз, а второй указатель перемещает по 2 элемента за раз. Таким образом, когда второй указатель достигнет конца, первый указатель будет посередине.
Ответ 2
Следующий код поможет вам получить средний элемент. Вам нужно использовать два указателя "быстрый" и "медленный". На каждом шаге быстрый указатель будет увеличиваться на два и медленнее будет увеличиваться на единицу. Когда список закончится, медленный указатель будет посередине.
Рассмотрим, что Node выглядит следующим образом:
class Node
{
int data;
Node next;
}
И LinkedList имеет метод getter для предоставления заголовка связанного списка
public Node getHead()
{
return this.head;
}
Ниже метод получит средний элемент списка (не зная размер списка)
public int getMiddleElement(LinkedList l)
{
return getMiddleElement(l.getHead());
}
private int getMiddleElement(Node n)
{
Node slow = n;
Node fast = n;
while(fast!=null && fast.next!=null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow.data;
}
Пример:
Если список 1-2-3-4-5, средний элемент равен 3
Если в списке 1-2-3-4 средний элемент равен 3
Ответ 3
В C, используя указатели, для полноты. Обратите внимание, что это основано на алгоритме Tortoise and Hare, который используется для проверки того, содержит ли связанный список цикл.
Наш node определяется как:
typedef struct node {
int val;
struct node *next;
} node_t;
Тогда наш алгоритм:
node_t *
list_middle (node_t *root)
{
node_t *tort = root;
node_t *hare = root;
while (hare != NULL && hare->next != NULL) {
tort = tort->next;
hare = hare->next->next;
}
return (tort);
}
Для списка с четным числом узлов возвращается node, обрабатывающий фактический центр (например, в списке из 10 узлов, это вернет node 6).
Ответ 4
Есть два возможных ответа: один для нечетного и один для четного, оба имеют один и тот же алгоритм
Для нечетных: один указатель перемещается на один шаг, а второй указатель перемещает два элемента как время и когда второй элемент достигает последнего элемента, элемента, в котором первый указатель, средний элемент. Очень легко для странных. Попробуйте: 1 2 3 4 5
Для четного: один и тот же, один указатель перемещается на один шаг, а второй указатель перемещает два элемента как время и когда второй элемент не может перейти к следующему элементу, элементу, в котором первый указатель, средний элемент. Попробуйте: 1 2 3 4
Ответ 5
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);
Ответ 6
Используя переменную размера, вы можете сохранить размер связанного списка.
public class LinkedList {
private Node headnode;
private int size;
public void add(int i){
Node node = new Node(i);
node.nextNode = headnode;
headnode = node;
size++;
}
public void findMiddleNode(LinkedList linkedList, int middle) {
Node headnode = linkedList.getHeadnode();
int count = -1;
while (headnode!=null){
count++;
if(count == middle){
System.out.println(headnode.data);
}else {
headnode = headnode.nextNode;
}
}
}
private class Node {
private Node nextNode;
private int data;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
}
public Node getHeadnode() {
return headnode;
}
public int getSize() {
return size;
}
}
Затем из клиентского метода найдите середину размера списка:
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(5);
linkedList.add(3);
linkedList.add(9);
linkedList.add(4);
linkedList.add(7);
linkedList.add(99);
linkedList.add(34);
linkedList.add(798);
linkedList.add(45);
linkedList.add(99);
linkedList.add(46);
linkedList.add(22);
linkedList.add(22);
System.out.println(linkedList.getSize());
int middle = linkedList.getSize()/2;
linkedList.findMiddleNode(linkedList, middle);
}
}
Я не знаю, лучше ли это, чем два способа node, но здесь вам также не нужно проходить через весь цикл.
Ответ 7
Использование С# для поиска среднего элемента связанного списка
static void Main(string[] args)
{
LinkedList<int> linked = new LinkedList<int>();
linked.AddLast(1);
linked.AddLast(3);
linked.AddLast(5);
linked.AddLast(6);
linked.AddFirst(12);
Console.WriteLine("Middle Element - "+ListMiddle<int>(linked));
Console.ReadLine(); }
public static T ListMiddle<T>(IEnumerable<T> input)
{
if (input == null)
return default(T);
var slow = input.GetEnumerator();
var fast = input.GetEnumerator();
while (slow.MoveNext())
{
if (fast.MoveNext())
{
if (!fast.MoveNext())
return slow.Current;
}
else
{
return slow.Current;
}
}
return slow.Current;
}
Ответ 8
Приведенные ниже методы Java находят середину связанного списка. Он использует два указателя: 1) медленные указатели, которые перемещаются на единицу в каждой итерации 2) быстрый указатель, который перемещается дважды в каждой итерации. Медленный указатель будет указывать на середину, когда быстрый достигает конца списка.
public SinglyLinkedListNode getMiddle(SinglyLinkedListNode list) {
if (list == null)
return null;
SinglyLinkedListNode fastPtr = list.next;
SinglyLinkedListNode slowPtr = list;
while (fastPtr != null) {
fastPtr = fastPtr.next;
if (fastPtr != null) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next;
}
}
return slowPtr;
}
Ответ 9
Для двусвязного списка с указанными указателями на головной и хвостовой узлы
мы можем использовать как голову, так и хвост
p = head;
q = tail;
while(p != q && p->next != q)
{
p = p->next;
q = q->prev;
}
return p;
Введение указателя на средний узел может быть вариантом, но функции, такие как
insertNode и deleteNode должны изменить этот указатель
Ответ 10
Код Python для среднего элемента с использованием метода двух указателей:
class Node:
def __init__(self,data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def printList(self):
temp=self.head
while(temp):
print(temp.data,end=" ")
temp=temp.next
def insertAtBeg(self,new_data):
new_node=Node(new_data)
if self.head is None:
self.head=new_node
return
new_node.next=self.head
self.head=new_node
def findMiddle(self):
fast_ptr=self.head
slow_ptr=self.head
if(self.head is not None):
while(fast_ptr is not None and fast_ptr.next is not None):
fast_ptr=fast_ptr.next.next
slow_ptr=slow_ptr.next
print('Middle Element is '+ str (slow_ptr.data))
if __name__=='__main__':
mylist=LinkedList()
mylist.insertAtBeg(10)
mylist.insertAtBeg(20)
mylist.insertAtBeg(30)
mylist.findMiddle()
Выход: средний элемент равен 20
Ответ 11
import java.util.*;
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(10);
linkedList.add(32);
linkedList.add(90);
linkedList.add(43);
linkedList.add(70);
linkedList.add(20);
linkedList.add(45);
int middle = linkedList.size()/2;
System.out.println(linkedList.get(middle));
}}
Ответ 12
Я добавляю свое решение, которое будет работать как для нечетного, так и для четного числа элементов, таких как
1-2-3-4-5 средний элемент 3
1-2-3-4 средний элемент 2,3
Он основан на том же принципе быстрого указателя и принципа медленного указателя, как упомянуто в некоторых других ответах в посте.
public class linkedlist{
Node head;
static class Node{
int data;
Node next;
Node(int d) { data = d; next=null; }
}
public static void main(String args[]){
linkedlist ll = new linkedlist();
Node one = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node five = new Node(5);
Node sixth = new Node(6);
Node seventh = new Node(7);
Node eight = new Node(8);
ll.head = one;
one.next = second;
second.next = third;
third.next = fourth;
fourth.next = five;
five.next = sixth;
sixth.next = seventh;
seventh.next = eight;
ll.printList();
ll.middleElement();
}
public void printList(){
Node n = head;
while( n != null){
System.out.print(n.data+ " ---> ");
n = n.next;
}
}
public void middleElement(){
Node headPointer = head;
Node headFasterPointer = head;
int counter = 0;
if(head != null){
while(headFasterPointer.next != null ){
if(headFasterPointer.next.next != null){
headFasterPointer = headFasterPointer.next.next;
headPointer = headPointer.next;
}
else
{
headFasterPointer = headFasterPointer.next;
}
counter++;
}
System.out.println();
System.out.println("The value of counter is "+ counter);
if(counter %2 == 0){
System.out.println("The middle element is " + headPointer.data +","+ headPointer.next.data);
} else
{
System.out.println("The middle element is " + headPointer.data );
}
}
}}
Ответ 13
Глупо использовать два указателя "быстрый" и "медленный". При этом оператор следующий используется в 1,5 раза. Оптимизация отсутствует.
Использование указателя для сохранения среднего элемента может помочь вам.
list* find_mid_1(list* ptr)
{
list *p_s1 = ptr, *p_s2 = ptr;
while (p_s2=p_s2->get_next())
{
p_s2 = p_s2->get_next();
if (!p_s2)
break;
p_s1 = p_s1->get_next();
}
return p_s1;
}