Для получения полного доступа
зарегистрируйтесь.
RSS

Все сниппеты с тэгом «linked list»



Сниппет,  C#

Reverse single linked list

Gravatar image
isxaker
  • Репутация: 8
  • Сниппеты: 4
  • Ревизии: 0

For reversing the linked list

public void Reverse()
{
	Node cur = _root;
	Node prev = null;

	while(cur != null)
	{
		Node next = cur.Next;
		cur.Next = prev;
		prev = cur;
		cur = next;
	}
	_root = prev;
}
Gravatar image
degree
  • Репутация: 2
  • Сниппеты: 1
  • Ревизии: 0

Используя O(1) по памяти находится возможное начало цикла в односвязном списке.

Соль решения в том, чтобы заставить 2 указателя бегать с разной скоростью. Как только один догоняет другой -- значит есть цикл. Если аккуратно посчитать, то пробежав еще с одинаковой скоростью от начала списка и с места встречи, новое место встречи будет началом цикла.

Полное описание задачи: https://leetcode.com/problems/linked-list-cycle-ii/

	public ListNode detectCycle(ListNode head) {
		if (head == null || head.next == null) return null;
		else if (head.next == head) return head;
		ListNode p1 = head, p2 = head;
		while (p2 != null) {
			p1 = p1.next;
			p2 = p2.next;
			if (p2 != null) p2 = p2.next;
			if (p1 == p2) break;
		}
		if (p2 == null) return null;
		while (head != p2) {
			head = head.next;
			p2 = p2.next;
		}
		return head;
	}