ping

Такое впечатление, что index в этом задании про linked list нумеруется не с нуля, а "как у людей" (с единицы): leetcode.com/explore/item/1290

узнал по проваленным юнит-тестам, а так вижу что особых упоминаний про это нет, разве что постоянно приписывают th (index'th element) -- но мне например совсем не очевидно, что это "догадайся сам, что это как у людей". И к чему тогда "Assume all nodes in the linked list are 0-indexed."?

А, не, мир не рухнул ) Это я сделал две ошибки так, что одна с другой провзаимодействовав выдала такой эффект )

По идее нет: при любой вставке/удалении придётся переделывать чуть ли не всю цепочку от head до tail

от места удаления/вставки и до самой head

до чего странные вопросы приходят порой в голову

@AK В функциональных языках наподобие Лиспа списки традиционно иммутабельные.

@AlexanderPetrov Я пока не настолько убился в F#, haskell и функциональный стиль в шарпе, чтобы знать о таких тонкостях. Так, просто прикинул "что если"

В дотнетных Immutable Collections реализован интересный подход: их можно создавать как мутабельные, а когда создание завершено, переводить в неизменяемые.

@AlexanderPetrov гм, и про это не слышал, спасибо за ссылку!

Как-то так выглядит:


[Test]
[TestCase(
	new string[] { "MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get" },
	new object[] { null, 1, 3, new int[] { 1, 2 }, 1, 1, 1 },
	new object[] { null, null, null, null, 2, null, 3 }
)]
[TestCase(
	new string[] { "MyLinkedList", "addAtIndex", "addAtIndex", "addAtIndex", "get" },
	new object[] { null, new int[] { 0, 10 }, new int[] { 0, 20 }, new int[] { 1, 30 }, 0 },
	new object[] { null, null, null, null, 20 }
)]
[TestCase(

Надо же, какие только не бывают реализации linked list! Я-то думал, что есть классический вариант "храним только head", потом "храним head + счётчик элементов" и самый типовой вариант "храним head, tail и счётчик"

public class MyLinkedList {

	private Node head = new Node(-1);
	private Node tail = new Node(-1);

	/** Initialize your data structure here. */
	public MyLinkedList()
	{
		head.next = tail;
		tail.prev = head;
	}

	/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
	public int Get(int index)
	{

		Node n = this.head.next;
		while (n != this.tail && n.next != this.tail && index > 0)
		{
			n = n.next;
			index--;
		}

		if (index != 0) return -1;

		return n.Value;

Что-то я не уверен, что стоило выносить в Node методы AddNext, AddBefore, RemoveMe - нарушается SRP, выигрыша в скорости нет, накладные расходы на хранение экземлярных методов - выше чем в случае когда просто класс из чисто данных

но вот по крайней мере leetcode утверждает, что это решение по скорости входит в мою группу

Гм, и по памяти даже лучше вышло, 37500 vs 37800