связанный список

[rrrFer]

а вы иллюстрацию не смотрели?

мы хотели ее посмотреть. но:

кстати, в файле ничего нет.

во всяком случае в libreoffice открывается пустой документ.

кол = 0
Засовываешь в словарь (мар) указатель на голову.
если список не пуст
     кол = кол + 1
пока (вечный цикл)
   голова = следующий элемент.
   если указатель на голову есть в мар - выход из цикла
   засунуть в мап указатель на голову
конец цикла

вывод кол.

время n*log(n)

а лучше я пока что не придумал, я думаю нужно больше информации о списке, может быть он отсортированный? - тогда задача тривиальна и реально решается за линейное время. Или может быть известно количество элементов в списке ? - тогда решается тоже за линейное..

[Sibedir]

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  PMyListItem = ^TMyListItem;
  TMyListItem = record
    Next: PMyListItem;
    Data: Integer;
    BlaBlaBla: string;
  end;

  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  FirstItem: PMyListItem;

implementation

function MyListCount (AFirst: PMyListItem): Integer;
var
  n: PMyListItem;
begin
  n := AFirst^.Next;
  if n = nil then
    Result := 0
  else begin
    AFirst^.Next := nil;
    Result := MyListCount (n);
    Inc (Result);
    AFirst^.Next := n;
  end;
end;

procedure MyListClear (AFirst: PMyListItem);
var
  n: PMyListItem;
begin
  n := AFirst^.Next;
  if n <> nil then begin
    AFirst^.Next := nil;
    MyListClear (n);
    AFirst^.Next := n;
    FreeMem (AFirst)
  end;
end;

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
var
  i, n1, n2: Integer;
  cur, next, circ: PMyListItem;
begin
  Randomize;
  n1 := Random (1024) + 1;
  n2 := Random (1024) + 1;
  Label1.Caption := 'Реально - ' + IntToStr (n1 + n2);

  New (FirstItem);
  cur := FirstItem;
  for i := 2 to n1 do begin
    New (next);
    cur^.Next := next;
    cur := next;
  end;

  circ := cur;

  for i := 1 to n2 do begin
    New (next);
    cur^.Next := next;
    cur := next;
  end;

  cur^.Next := circ;

  n1 := MyListCount (FirstItem);
  Label2.Caption := 'Посчитано - ' + IntToStr (n1);
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  MyListClear (FirstItem);
end;

end.

Теперь главное чтоб стека хватило.

[leonid_v]

Сообщение от rrrFer

Или может быть известно количество элементов в списке ? - тогда решается тоже за линейное..

это что надо найти!

[Sibedir]

Хотелось бы еще отметить, что приведенные мной функции MyListCount и MyListClear работают только для кольцевого не пустого списка.
Вот подкорректировал их для более общего случая

const
  nil_1: PMyListItem = Pointer ($00000001);

function MyListCount (AFirst: PMyListItem): Integer;
var
  n: PMyListItem;
begin
  if (AFirst = nil) or (AFirst^.Next = nil_1) then
    Result := 0
  else begin
    n := AFirst^.Next;
    AFirst^.Next := nil_1;
    Result := MyListCount (n);
    Inc (Result);
    AFirst^.Next := n;
  end;
end;

procedure MyListClear (AFirst: PMyListItem);
var
  n: PMyListItem;
begin
  if (AFirst <> nil) and (AFirst^.Next <> nil_1) then begin
    n := AFirst^.Next;
    AFirst^.Next := nil_1;
    MyListClear (n);
    FreeMem (AFirst)
  end;
end;

[rrrFer]

Sibedir
угу, прикольно )

но рекурсию можно не исопльзовать (стек особо не тиранить), но также обнулять указатели next всех пройденных элементов. При этом список сломается и память утечет, а чтобы все сохранить можно указаетли на все пройденные элементы засунуть в еще один список - тогда и паять можно корректно освободить и исходный список со всеми его петлями восстановить.

На плюсиках как-то так:

#include <iostream>
template<typename T>
struct Node {
  T value_;
  Node<T> *next_;
  Node<T>(T value, Node<T> *next = nullptr)
    : value_(value)
    , next_(next) { 
  }
};

template<typename T> // добавляет элемент в стек
Node<T>* push(Node<T> *head, T value) {
  if (nullptr == head)
    return head = new Node<T>(value);
  return new Node<T>(value, head);
}

template<typename T> // зацикливает стек
bool addCycle(Node<T> *head, int idxA) {
  Node<T> *a = nullptr, *b = head;
  if (nullptr == b) 
    return false;
  while (b->next_) {
    if (0 == --idxA) 
      a = b;
    b = b->next_;
  }
  if (nullptr == a)
    return false;
  b->next_ = a;
  return true;
}
    
template<typename T>
Node<Node<T>*> *node2pnode(Node<T> *head) {
  Node<T> *t = nullptr;
  Node<Node<T>*> *headP = nullptr;
  
  while (head) {
    headP = push(headP, head);
    
    t = head;
    head = head->next_;
    t->next_ = nullptr;
  }
  return headP;
}

template<typename T>
int count(Node<T> *head) {
  auto *t = head;
  int n = 0;
  while (t) {
    ++n;
    t = t->next_;
  }
  return n;
}
    
int main() {
  Node<int> *head = nullptr;
  
  for (int i = 0; i < 12; ++i)
    head = push(head, i);
  
  addCycle(head, 5);
  
  auto headP = node2pnode(head);
  
  std::cout << count(headP) - 1;
  
  return 0;
}

Память я не освобождал и список исходный не восстанавливал. но это возможно, я уверен .

[Sibedir]

2 rrrFer
Нужна именно рекурсия

Сообщение от leonid_v

подсчитать количество элементов массива за один проход не используя дополнительной структуры?

Я так это понял

[still_alive]

Решал эту задачу на собеседовании)

Пускаем от начала списка два указателя - один из них движется со скоростью 1, другой со скоростью 2. В какой-то момент быстрый догонит медленный и они встретятся. Теперь пускаем один указатель от начала списка, а другой от точки встречи - оба со скоростью 1. В общем там из математики следует, что они встретятся точно в начале цикла. Требования по памяти и асимптотике при этом удовлетворяются. Дальше элементарщина)

[Sibedir]

Круто, still_alive. Так и думал, что задача решается по средствам математики, но ни чего дельного в голову не пришло, а искать не хотелось.

Добавлено -----------------------------------------------------------------------
Кстати, а как быть с

Сообщение от leonid_v

подсчитать количество элементов массива за один проход не используя дополнительной структуры?

Хотя признаю, можно извратиться и запихнуть это в рекурсию, а потом еще на ASM'е извратиться и избавиться от записи (уже не нужных) значений в стек, а использовать только регистры (ну может пару значений в стеке).

[rrrFer]

still_alive
это очень круто и работает вроде-бы, а доказать у меня не получилось... Я решил сначала вычислить через сколько клеток 2 указателя (с разными скоростями) встретятся...
получилось равенство, которое я не знаю как решать )

Я разделил список на 2 отрезка - линейный и циклический (А и В). и пусть p1 - медленный, р2 - быстрый указатели.

ясно что раньше чем через А шагов указатели встретица не могут.
через А шагов между ними будет А mod В элементов списка.
а встретятся они через x шагов, которое нужно определить из равенства:
x mod B = (2*x + (A mod B)) mod B
и при этом решить надо в целых числах... подскажи как ты это сделал? или намекни правильный запрос гуглу, пожалсто )

[Sibedir]

Есть 2 путевых обходчика и наш стек. Стек состоит из хвоста и цикла.
Пусть:
А - длина хвоста
B - длина цикла
До первой встречи обходчики пройдут (A+x) и (A+nB+x) соответственно. Из условия их скорости ясно, что:
2(A+x) = (A+nB+x)
далее
2A+2x = A+nB+x
2A-А = nB+x-2x
A = nB-x
а выражение (nB-x) есть ничто иное, как расстояние, которое нужно пройти второму со скоростью 1 чтобы завершить цикл, ведь x от начала цикла он уже прошел (x+(nB-x) = nB). Следовательно, если первый начнет сначала, а второй продолжит, то через A шагов они оба окажутся на первом элементе цикла.

вычислить через сколько клеток 2 указателя встретятся ~ найти A+x
1. A+x = nB
2. n = (A+x)/B
3. можно легко доказать, что при любом положении обходчиков на цикле второй догонит первого менее чем за В (при В>1) ходов (не сможет его перескочить (каждый ход расстояние м/у ними уменьшается на 1 и в итоге станет 0 (палюбому)), перескок возможен только при сторости второго >2).
4. т.к. x<B => n = (A div B)+1
5. A+x = B*((A div B)+1)