import 'dart:math';
import 'package:test/test.dart';
class Node {
int value;
Node? next = null;
Node(this.value);
int get nodeValue {
return this.value;
}
Node? get nextNode {
return this.next;
}
}
class LinkedList {
Node? _headNode;
Node? _tailNode;
Node? get head {
return this._headNode;
}
Node? get tail {
return this._tailNode;
}
void insert(Node? newNode) {
if (head == null) {
this._headNode = newNode;
this._tailNode = newNode;
} else {
this._tailNode?.next = newNode;
this._tailNode = this._tailNode?.next;
}
}
}
Node createNode(int value) {
return Node(value);
}
Node? findCyclicNode(Node? headNode) {
Node? fastNode = headNode;
Node? slowNode = headNode;
while (fastNode != null && fastNode.next != null) {
slowNode = slowNode?.next;
fastNode = fastNode.next?.next;
if (slowNode == fastNode) {
break;
}
}
if (slowNode == fastNode) {
slowNode = headNode;
while (slowNode != fastNode) {
slowNode = slowNode?.next;
fastNode = fastNode?.next;
}
return slowNode;
} else {
return null;
}
}
void main() {
LinkedList linkedList = LinkedList();
List<Node> allNodes = <Node>[];
for (var i = 0; i <= 10; i++) {
Node newNode = createNode(i);
linkedList.insert(newNode);
allNodes.add(newNode);
}
Node? tail = linkedList.tail;
Random random = new Random();
test(('test 1'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 2'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 3'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 4'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 5'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 6'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
test(('test 7'), () {
int randomIndex = random.nextInt(9);
tail?.next = allNodes[randomIndex];
Node? cycleNode = findCyclicNode(linkedList.head);
expect(cycleNode, equals(allNodes[randomIndex]));
});
}