commit 023cdd3a0f8e6375e1a21008305b080cb60af61c
parent fe8e30e5f0b01c424cb09d05270b3e7d56b662fe
Author: ling0x <ling0x@users.noreply.github.com>
Date: Sun, 6 Sep 2026 18:03:21 +0100
linked list cycles
Diffstat:
11 files changed, 741 insertions(+), 0 deletions(-)
diff --git a/src/lib.rs b/src/lib.rs
@@ -1,5 +1,6 @@
pub mod array;
pub mod hash_table;
+pub mod linked_list;
#[cfg(test)]
pub mod test_utils;
diff --git a/src/linked_list/linked_list_cycle.rs b/src/linked_list/linked_list_cycle.rs
@@ -0,0 +1,13 @@
+//! Given head, the head of a linked list, determine if the linked list has
+//! a cycle in it.
+//!
+//! There is a cycle in a linked list if there is some node in the list that
+//! can be reached again by continuously following the next pointer.
+//! Internally, pos is used to denote the index of the node that tail's next
+//! pointer is connected to. Note that pos is not passed as a parameter.
+//!
+//! Return true if there is a cycle in the linked list. Otherwise, return false.
+
+fn solution_1() -> bool {
+ true
+}
diff --git a/src/linked_list/mod.rs b/src/linked_list/mod.rs
@@ -0,0 +1 @@
+pub mod linked_list_cycle;
diff --git a/ts/.gitignore b/ts/.gitignore
@@ -0,0 +1 @@
+node_modules
diff --git a/ts/package-lock.json b/ts/package-lock.json
@@ -0,0 +1,408 @@
+{
+ "name": "leetcode-ts",
+ "version": "0.1.0",
+ "lockfileVersion": 3,
+ "requires": true,
+ "packages": {
+ "": {
+ "name": "leetcode-ts",
+ "version": "0.1.0",
+ "devDependencies": {
+ "@types/node": "*",
+ "typescript": "*"
+ }
+ },
+ "node_modules/@types/node": {
+ "version": "26.1.1",
+ "resolved": "https://registry.npmjs.org/@types/node/-/node-26.1.1.tgz",
+ "integrity": "sha512-nxAkRSVkN1Y0JC1W8ky/fTfkGsMmcrRsbx+3XoZE+rMOX71kLYTV7fLXpqud1GpbpP5TuffXFqfX7fH2GgZREw==",
+ "dev": true,
+ "license": "MIT",
+ "dependencies": {
+ "undici-types": "~8.3.0"
+ }
+ },
+ "node_modules/@typescript/typescript-aix-ppc64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-aix-ppc64/-/typescript-aix-ppc64-7.0.2.tgz",
+ "integrity": "sha512-MTKKkWB7p/0E9xi1d1tHtZ5PiLkGEMIq88pK2CubZjOsLtYTLqhgIgi6zepFa+9GHZ6h05NMCkQxGKiPXMxXtQ==",
+ "cpu": [
+ "ppc64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "aix"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-darwin-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-darwin-arm64/-/typescript-darwin-arm64-7.0.2.tgz",
+ "integrity": "sha512-gowzar9MwS/aRWp6f3a4KUqzRjAZjOsmGNCM6LcTgXum+dBfgsBVMN+AgvOCCbguXyick6LJhpBszxMebJ8syA==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "darwin"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-darwin-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-darwin-x64/-/typescript-darwin-x64-7.0.2.tgz",
+ "integrity": "sha512-SZ9xZInqApNlNGc9s0W1VSsktYSOe9cFqNOIqmN1Gs8SmkjKZYFt017G4VwPxASInODuAdbTW7sXiFUf893RgA==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "darwin"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-freebsd-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-freebsd-arm64/-/typescript-freebsd-arm64-7.0.2.tgz",
+ "integrity": "sha512-W5NH4y/J0plIIS5b2xvTEkU7JFxyqdMAOgf+Ilhl0vHQXKO5dZoxd+C/jEtq56c4F3wk71RB4BMRQ2XdI+bwYQ==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "freebsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-freebsd-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-freebsd-x64/-/typescript-freebsd-x64-7.0.2.tgz",
+ "integrity": "sha512-UMGDx5sTpzNw3WiPebH7l90IWfJggEd+egHt/q6p7/Cm3zqoV7VxkGXt+3DxPIw8CcmvAB0j3sVVfbhX+M4Tpw==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "freebsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-arm": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-arm/-/typescript-linux-arm-7.0.2.tgz",
+ "integrity": "sha512-gffT3xPz9sR7j/YJExkyPntrI0P2EP9XbOyWzth2/Gs0RstK+90RBcO0ncXoXy/beYll1SXw846Nf2zdnEz0QQ==",
+ "cpu": [
+ "arm"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-arm64/-/typescript-linux-arm64-7.0.2.tgz",
+ "integrity": "sha512-Qh4eU4/y3yDjnfjjyPYihMj5/ODIlmt+Bzu17OI+fiSRDW57QmU5SiN63exPRNJPKUzcc1INa1NXdrJ+MqHjUQ==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-loong64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-loong64/-/typescript-linux-loong64-7.0.2.tgz",
+ "integrity": "sha512-uEHck9i8hoAzXPiYRib1O7miOnz23SxIeVl6F4LXox+qov1K35jHcEW6VHKvZI+pyvl7fZEP4MCU5LYvIq1GuQ==",
+ "cpu": [
+ "loong64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-mips64el": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-mips64el/-/typescript-linux-mips64el-7.0.2.tgz",
+ "integrity": "sha512-R4KvAMnE43W5Qeqb0Ly56O3mWMWIAgsMyz36DCaycd5nbg/9kzm0liw3JocfRqyJY0KPmzFjbswozXyW0DnIYA==",
+ "cpu": [
+ "mips64el"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-ppc64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-ppc64/-/typescript-linux-ppc64-7.0.2.tgz",
+ "integrity": "sha512-DORx5b3sd/4S7eayxm4FQv+A7CrkUIGRaHiwI8oiHTAI1fAPWhF4J0vAlkC8biAlHSVVwxMQ3tjZ2/DVbnQiiA==",
+ "cpu": [
+ "ppc64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-riscv64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-riscv64/-/typescript-linux-riscv64-7.0.2.tgz",
+ "integrity": "sha512-wf0jqEDOjrPRnKwYRyyJDRo11KMbvMFrU+q4zqKyChODBzvlkbhNQfKvLxQCcwTpdDaXSHZTVuh0JoCrKCUMHQ==",
+ "cpu": [
+ "riscv64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-s390x": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-s390x/-/typescript-linux-s390x-7.0.2.tgz",
+ "integrity": "sha512-IkwJc3L7yhytWd/ewjyxNDfOmswCm9GWMJT/ue/dU4aZNbwZeYAetq42VyLmsmSjvoX7z74X6ZaYCtzAr0EuGw==",
+ "cpu": [
+ "s390x"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-linux-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-linux-x64/-/typescript-linux-x64-7.0.2.tgz",
+ "integrity": "sha512-EYdf2cNg7rgCWJnxCdJ+F3V39O8ihb37eHAu1LK8oAFizgTQbPOK7zHHXbPt8rX24COqODXeI3sIf0fCXG7H/A==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "linux"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-netbsd-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-netbsd-arm64/-/typescript-netbsd-arm64-7.0.2.tgz",
+ "integrity": "sha512-+polYF4MF04aPpO5FTkHran9yUQDSXqy5GiSDKpsll5jy3l3+g9QLhpf39T+ePtefhXLOGrLl0QIjkQP6VnelA==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "netbsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-netbsd-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-netbsd-x64/-/typescript-netbsd-x64-7.0.2.tgz",
+ "integrity": "sha512-8YIT0EHM/3dq10ZOVF/A7pc/YSMtbcecct4rWtexrnSCHOPcpC2KTLXfTCR6vDpnSiY12heNb1GiN/wu+T/FyA==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "netbsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-openbsd-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-openbsd-arm64/-/typescript-openbsd-arm64-7.0.2.tgz",
+ "integrity": "sha512-APT8+ClYnuYm1u9+kgGXoMj2VzWzcymwh2gNSQVySHfkRDGOTVkoWLjCmOQSaO+PoqQ57B0flRp9SA+7GnnkzQ==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "openbsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-openbsd-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-openbsd-x64/-/typescript-openbsd-x64-7.0.2.tgz",
+ "integrity": "sha512-yX7s+Q0Dln0Dt9tEzZsAjXXR/+ytBM7AlglaqyeMPxQszJ1JhlJdZ6jLA+IzldHtflX81em7lDao1xXu+aRRkg==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "openbsd"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-sunos-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-sunos-x64/-/typescript-sunos-x64-7.0.2.tgz",
+ "integrity": "sha512-dLJDGaLZ1D4HPQn62u1n8mBDkJREwMsAkCdkwd4Ieqw+x3TUyTsqY0YiBCtE6H6OzzgGk3iuZ3vFWRS+E8/d1g==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "sunos"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-win32-arm64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-win32-arm64/-/typescript-win32-arm64-7.0.2.tgz",
+ "integrity": "sha512-Gyl1Vy6OsWesLzmq+EP0Fb7b4Nid5232AvcA2SFcdYreldpNtYFFofPjnt62y9hQy7VTaZp65ICJjuAQRaVcIQ==",
+ "cpu": [
+ "arm64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "win32"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/@typescript/typescript-win32-x64": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/@typescript/typescript-win32-x64/-/typescript-win32-x64-7.0.2.tgz",
+ "integrity": "sha512-0BQ3HkAHHlKLSp1qRvf3SUhGpGsDuhB/jgFw75guyqbxJqEaS0Cw/VFO8i2nHglJUzQCRtMMR/IBAKE3ETMC4g==",
+ "cpu": [
+ "x64"
+ ],
+ "dev": true,
+ "license": "Apache-2.0",
+ "optional": true,
+ "os": [
+ "win32"
+ ],
+ "engines": {
+ "node": ">=16.20.0"
+ }
+ },
+ "node_modules/typescript": {
+ "version": "7.0.2",
+ "resolved": "https://registry.npmjs.org/typescript/-/typescript-7.0.2.tgz",
+ "integrity": "sha512-8FYau96o3NKOhbjKi/qNvG/W5jhzxkbdm5sj9AbZ/5T5sWqn3hJgLfGx27sRKZWTvyzCP8dLRBTf5tBTSRVUNA==",
+ "dev": true,
+ "license": "Apache-2.0",
+ "bin": {
+ "tsc": "bin/tsc"
+ },
+ "engines": {
+ "node": ">=16.20.0"
+ },
+ "optionalDependencies": {
+ "@typescript/typescript-aix-ppc64": "7.0.2",
+ "@typescript/typescript-darwin-arm64": "7.0.2",
+ "@typescript/typescript-darwin-x64": "7.0.2",
+ "@typescript/typescript-freebsd-arm64": "7.0.2",
+ "@typescript/typescript-freebsd-x64": "7.0.2",
+ "@typescript/typescript-linux-arm": "7.0.2",
+ "@typescript/typescript-linux-arm64": "7.0.2",
+ "@typescript/typescript-linux-loong64": "7.0.2",
+ "@typescript/typescript-linux-mips64el": "7.0.2",
+ "@typescript/typescript-linux-ppc64": "7.0.2",
+ "@typescript/typescript-linux-riscv64": "7.0.2",
+ "@typescript/typescript-linux-s390x": "7.0.2",
+ "@typescript/typescript-linux-x64": "7.0.2",
+ "@typescript/typescript-netbsd-arm64": "7.0.2",
+ "@typescript/typescript-netbsd-x64": "7.0.2",
+ "@typescript/typescript-openbsd-arm64": "7.0.2",
+ "@typescript/typescript-openbsd-x64": "7.0.2",
+ "@typescript/typescript-sunos-x64": "7.0.2",
+ "@typescript/typescript-win32-arm64": "7.0.2",
+ "@typescript/typescript-win32-x64": "7.0.2"
+ }
+ },
+ "node_modules/undici-types": {
+ "version": "8.3.0",
+ "resolved": "https://registry.npmjs.org/undici-types/-/undici-types-8.3.0.tgz",
+ "integrity": "sha512-j375ScV60dom+YkPFIfTLcOiPxkN/buHz5GobjLhixFuANaNs3C9l4GmrWqejgXWJ7BbJcFYpTEUkS1Ge8bpZQ==",
+ "dev": true,
+ "license": "MIT"
+ }
+ }
+}
diff --git a/ts/package.json b/ts/package.json
@@ -0,0 +1,14 @@
+{
+ "name": "leetcode-ts",
+ "version": "0.1.0",
+ "private": true,
+ "type": "module",
+ "scripts": {
+ "test": "node --test",
+ "typecheck": "tsc --noEmit"
+ },
+ "devDependencies": {
+ "typescript": "*",
+ "@types/node": "*"
+ }
+}
diff --git a/ts/src/linked_list/-1, b/ts/src/linked_list/-1,
@@ -0,0 +1,2 @@
+
+
diff --git a/ts/src/linked_list/index.ts b/ts/src/linked_list/index.ts
@@ -0,0 +1 @@
+export * from "./linkedListCycle.ts";
diff --git a/ts/src/linked_list/linkedListCycle.test.ts b/ts/src/linked_list/linkedListCycle.test.ts
@@ -0,0 +1,47 @@
+import { test } from "node:test";
+import assert from "node:assert/strict";
+
+import { buildList, solution3, type ListNode } from "./linkedListCycle.ts";
+
+interface CycleCase {
+ name: string;
+ values: number[];
+ pos: number; // index the tail links back to, or -1 for no cycle
+ expected: boolean;
+}
+
+function fullCases(): CycleCase[] {
+ return [
+ { name: "case_1", values: [3, 2, 0, -4], pos: 1, expected: true },
+ { name: "case_2", values: [1, 2], pos: 0, expected: true },
+ { name: "case_3", values: [1], pos: -1, expected: false },
+ { name: "case_4", values: [], pos: -1, expected: false },
+ { name: "case_5", values: [1, 2], pos: -1, expected: false },
+ {
+ name: "case_6",
+ values: [
+ -21, 10, 17, 8, 4, 26, 5, 35, 33, -7, -16, 27, -12, 6, 29, -12, 5, 9,
+ 20, 14, 14, 2, 13, -24, 21, 23, -21, 5,
+ ],
+ pos: -1,
+ expected: false,
+ },
+ { name: "case_7", values: [1, 1, 1, 1], pos: -1, expected: false },
+ ];
+}
+
+function runSolverCases(
+ solverName: string,
+ solver: (head: ListNode | null) => boolean,
+ cases: CycleCase[],
+): void {
+ for (const c of cases) {
+ test(`${solverName}_${c.name}`, () => {
+ const head = buildList(c.values, c.pos);
+ assert.equal(solver(head), c.expected);
+ });
+ }
+}
+
+// runSolverCases("solution1", solution1, fullCases());
+runSolverCases("solution3", solution3, fullCases());
diff --git a/ts/src/linked_list/linkedListCycle.ts b/ts/src/linked_list/linkedListCycle.ts
@@ -0,0 +1,239 @@
+/**
+ * Given head, the head of a linked list, determine if the linked list
+ * has a cycle in it.
+ *
+ * There is a cycle in a linked list if there is some node in the list
+ * that can be reached again by continuously following the next pointer.
+ * Internally, pos is used to denote the index of the node that tail's
+ * next pointer is connected to. Note that pos is not passed as a
+ * parameter.
+ *
+ * Return true if there is a cycle in the linked list. Otherwise,
+ * return false.
+ */
+
+export class ListNode {
+ val: number;
+ next: ListNode | null;
+ constructor(val?: number, next?: ListNode | null) {
+ this.val = val === undefined ? 0 : val;
+ this.next = next === undefined ? null : next;
+ }
+}
+
+/**
+ * Build a linked list from `values`. If `pos >= 0`, the tail's `next` is
+ * connected back to the node at index `pos` to form a cycle. `pos = -1`
+ * leaves the list acyclic. Returns the head (or null for an empty list).
+ */
+export function buildList(values: number[], pos: number): ListNode | null {
+ if (values.length === 0) return null;
+
+ const nodes = values.map((v) => new ListNode(v));
+ for (let i = 0; i < nodes.length - 1; i++) {
+ nodes[i].next = nodes[i + 1];
+ }
+ if (pos >= 0) {
+ nodes[nodes.length - 1].next = nodes[pos];
+ }
+ return nodes[0];
+}
+
+/**
+ * Definition for singly-linked list.
+ * class ListNode {
+ * val: number
+ * next: ListNode | null
+ * constructor(val?: number, next?: ListNode | null) {
+ * this.val = (val===undefined ? 0 : val)
+ * this.next = (next===undefined ? null : next)
+ * }
+ * }
+ */
+
+// First attempt
+//
+// Failed (only check 1 at a time, which isnt enough)
+// Failed on case: [-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,
+// 14,2,13,-24,21,23,-21,5] (should be false)
+export function solution1(head: ListNode | null): boolean {
+ if (!head) {
+ console.log("Head is empty. Return false");
+ return false;
+ }
+
+ let prev = null;
+ let current = head;
+
+ while (current.next) {
+ if (!current.next.next) return false;
+
+ console.log(
+ `Current: ${current.val}, next: ${current.next.val}, next's next ${current.next.next.val}`,
+ );
+
+ prev = current;
+ current = current.next;
+
+ if (prev.next === current) {
+ console.log(`Prev's next: ${prev.next.val} === Current: ${current.val}`);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+// Second attempt (two-pointer / sliding-window in same direction to detect
+// lapse)
+//
+// Failed (only checks 2 at a time, which isnt enough)
+// Failed on case [1,1,1,1] (should be false)
+export function solution2(head: ListNode | null): boolean {
+ console.log("====================");
+ console.log("Running test");
+
+ if (!head) {
+ console.log("Test is empty");
+ return false;
+ }
+
+ let next = head.next;
+ if (!next) {
+ console.log("Test only has 1 element, which isn't a cycle by default.");
+ return false;
+ }
+
+ // Log the current head and the next head
+ console.log(
+ `Head ${head.val}, next ${next.val}, next's next ${next.next?.val}, next's next's next ${next.next?.next?.val}, next's next's next's next ${next.next?.next?.next?.val}, next's next's next's next's next ${next.next?.next?.next?.next?.val}`,
+ );
+
+ let sliding_window: { a: number; b: number }[] = [
+ { a: head.val, b: next.val },
+ ];
+
+ // While the list still has more vertices, keep looping through it
+ while (next) {
+ if (!next.next) {
+ console.log("The list has been exhausted without any cycles.");
+ return false;
+ }
+
+ // If the next one exists, then add the next two to the sliding windows list
+ if (next.next) {
+ let next_pair: { a: number; b: number } = {
+ a: next.val,
+ b: next.next.val,
+ };
+ console.log("Next pair: ", next_pair);
+
+ const next_pair_already_exist = sliding_window.find(
+ (pair) => pair.a === next_pair.a && pair.b === next_pair.b,
+ );
+
+ if (next_pair_already_exist) {
+ console.log(
+ "Sliding window list already includes the next two pairs -> cycle detected",
+ );
+ return true;
+ }
+
+ sliding_window.push(next_pair);
+
+ // move to the next one
+ next = next.next;
+ }
+
+ console.log("Current state of the sliding Window: ", sliding_window);
+ }
+
+ console.log("Not a cycle");
+ return false;
+}
+
+// Third attempt (need a verification step to verify that not only the pair
+// exists but also is not terminating, if any pair terminates the list, then
+// its not a cycle by default - we basically need a proof that the list doesn't
+// terminate, even though the pairs lapse/repeat in the list)
+//
+// Success (Runtime: 1333ms, Memory: 63.33MB)
+export function solution3(head: ListNode | null): boolean {
+ console.log("====================");
+ console.log("Running test");
+
+ if (!head) {
+ console.log("Test is empty");
+ return false;
+ }
+
+ let next = head.next;
+ if (!next) {
+ console.log("Test only has 1 element, which isn't a cycle by default.");
+ return false;
+ }
+
+ // Log the current head and the next head
+ console.log(
+ `Head ${head.val}, next ${next.val}, next's next ${next.next?.val}, next's next's next ${next.next?.next?.val}, next's next's next's next ${next.next?.next?.next?.val}, next's next's next's next's next ${next.next?.next?.next?.next?.val}`,
+ );
+
+ let index = 0;
+ let sliding_window: {
+ a: { val: number; pos: number };
+ b: { val: number; pos: number };
+ }[] = [
+ {
+ a: { val: head.val, pos: index },
+ b: { val: next.val, pos: index + 1 },
+ },
+ ];
+
+ // While the list still has more vertices, keep looping through it
+ while (next) {
+ // Increment the index counter
+ index += 1;
+
+ if (!next.next) {
+ console.log("The list terminates without any cycles.");
+ return false;
+ }
+
+ // If the next one exists, then add the next two to the sliding windows list
+ if (next.next) {
+ let next_pair: {
+ a: { val: number; pos: number };
+ b: { val: number; pos: number };
+ } = {
+ a: { val: next.val, pos: index },
+ b: { val: next.next.val, pos: index + 1 },
+ };
+ console.log("Next pair: ", next_pair);
+
+ const next_pair_already_exist = sliding_window.findLast(
+ (pair) =>
+ pair.a.val === next_pair.a.val && pair.b.val === next_pair.b.val,
+ );
+
+ if (next_pair_already_exist) {
+ console.log("Sliding window list already includes the next two pairs");
+ // Check if the next pair is terminating
+ if (next.next.next && next.next.next.next) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ sliding_window.push(next_pair);
+
+ // move to the next one
+ next = next.next;
+ }
+
+ console.log("Current state of the sliding Window: ", sliding_window);
+ }
+
+ console.log("Not a cycle");
+ return false;
+}
diff --git a/ts/tsconfig.json b/ts/tsconfig.json
@@ -0,0 +1,14 @@
+{
+ "compilerOptions": {
+ "target": "ESNext",
+ "module": "NodeNext",
+ "moduleResolution": "NodeNext",
+ "rewriteRelativeImportExtensions": true,
+ "verbatimModuleSyntax": true,
+ "strict": true,
+ "noEmit": true,
+ "skipLibCheck": true,
+ "types": ["node"]
+ },
+ "include": ["src"]
+}
