Linked Lists

from __future__ import annotations


class ListNode:
    """One node of a singly linked list."""

    def __init__(self, val: int, next: ListNode | None = None):
        self.val = val
        self.next = next


def merge_two_lists(a: ListNode | None, b: ListNode | None) -> ListNode | None:
    """Merges two sorted lists into one sorted list by relinking their nodes."""
    # A placeholder in front of the result, so the first append isn't a special case.
    dummy = ListNode(0)
    tail = dummy
    while a is not None and b is not None:
        # Take the smaller head. On a tie take from a, so equal values keep their order.
        if a.val <= b.val:
            tail.next = a
            tail = a
            a = a.next
        else:
            tail.next = b
            tail = b
            b = b.next
    # One list ran out. The other is already sorted, so attach the rest of it whole.
    tail.next = a if a is not None else b
    return dummy.next


def build_list(values: list[int]) -> ListNode | None:
    head = None
    for value in reversed(values):
        head = ListNode(value, head)
    return head


def format_list(head: ListNode | None) -> str:
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.val))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


if __name__ == "__main__":
    print(format_list(merge_two_lists(build_list([1, 2, 4]), build_list([1, 3, 4]))))  # 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None
    print(format_list(merge_two_lists(build_list([]), build_list([]))))  # None
    print(format_list(merge_two_lists(build_list([]), build_list([0]))))  # 0 -> None

// One node of a singly linked list.
export class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// Merges two sorted lists into one sorted list by relinking their nodes.
export function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  // A placeholder in front of the result, so the first append isn't a special case.
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    // Take the smaller head. On a tie take from a, so equal values keep their order.
    if (a.val <= b.val) {
      tail.next = a;
      tail = a;
      a = a.next;
    } else {
      tail.next = b;
      tail = b;
      b = b.next;
    }
  }
  // One list ran out. The other is already sorted, so attach the rest of it whole.
  tail.next = a ?? b;
  return dummy.next;
}

function buildList(values: number[]): ListNode | null {
  let head: ListNode | null = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
  return head;
}

function formatList(head: ListNode | null): string {
  const parts: string[] = [];
  for (let node = head; node !== null; node = node.next) parts.push(String(node.val));
  parts.push("null");
  return parts.join(" -> ");
}

console.log(formatList(mergeTwoLists(buildList([1, 2, 4]), buildList([1, 3, 4])))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
console.log(formatList(mergeTwoLists(buildList([]), buildList([])))); // null
console.log(formatList(mergeTwoLists(buildList([]), buildList([0])))); // 0 -> null

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// ListNode is one node of a singly linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// mergeTwoLists merges two sorted lists into one sorted list by relinking
// their nodes.
func mergeTwoLists(a, b *ListNode) *ListNode {
	// A placeholder in front of the result, so the first append isn't a special case.
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		// Take the smaller head. On a tie take from a, so equal values keep their order.
		if a.Val <= b.Val {
			tail.Next = a
			tail = a
			a = a.Next
		} else {
			tail.Next = b
			tail = b
			b = b.Next
		}
	}
	// One list ran out. The other is already sorted, so attach the rest of it whole.
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

func buildList(values []int) *ListNode {
	var head *ListNode
	for i := len(values) - 1; i >= 0; i-- {
		head = &ListNode{Val: values[i], Next: head}
	}
	return head
}

func formatList(head *ListNode) string {
	parts := []string{}
	for node := head; node != nil; node = node.Next {
		parts = append(parts, strconv.Itoa(node.Val))
	}
	parts = append(parts, "nil")
	return strings.Join(parts, " -> ")
}

func main() {
	fmt.Println(formatList(mergeTwoLists(buildList([]int{1, 2, 4}), buildList([]int{1, 3, 4})))) // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> nil
	fmt.Println(formatList(mergeTwoLists(buildList([]int{}), buildList([]int{}))))               // nil
	fmt.Println(formatList(mergeTwoLists(buildList([]int{}), buildList([]int{0}))))              // 0 -> nil
}

using System;
using System.Collections.Generic;

public class Solution
{
    // One node of a singly linked list.
    public class ListNode
    {
        public int Val;
        public ListNode? Next;

        public ListNode(int val, ListNode? next = null)
        {
            Val = val;
            Next = next;
        }
    }

    // Merges two sorted lists into one sorted list by relinking their nodes.
    public static ListNode? MergeTwoLists(ListNode? a, ListNode? b)
    {
        // A placeholder in front of the result, so the first append isn't a special case.
        var dummy = new ListNode(0);
        var tail = dummy;
        while (a != null && b != null)
        {
            // Take the smaller head. On a tie take from a, so equal values keep their order.
            if (a.Val <= b.Val)
            {
                tail.Next = a;
                tail = a;
                a = a.Next;
            }
            else
            {
                tail.Next = b;
                tail = b;
                b = b.Next;
            }
        }
        // One list ran out. The other is already sorted, so attach the rest of it whole.
        tail.Next = a ?? b;
        return dummy.Next;
    }

    static ListNode? BuildList(int[] values)
    {
        ListNode? head = null;
        for (int i = values.Length - 1; i >= 0; i--) head = new ListNode(values[i], head);
        return head;
    }

    static string FormatList(ListNode? head)
    {
        var parts = new List<string>();
        for (var node = head; node != null; node = node.Next) parts.Add(node.Val.ToString());
        parts.Add("null");
        return string.Join(" -> ", parts);
    }

    public static void Main()
    {
        Console.WriteLine(FormatList(MergeTwoLists(BuildList(new[] { 1, 2, 4 }), BuildList(new[] { 1, 3, 4 })))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
        Console.WriteLine(FormatList(MergeTwoLists(BuildList(new int[0]), BuildList(new int[0])))); // null
        Console.WriteLine(FormatList(MergeTwoLists(BuildList(new int[0]), BuildList(new[] { 0 })))); // 0 -> null
    }
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // One node of a singly linked list.
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // Merges two sorted lists into one sorted list by relinking their nodes.
    static ListNode mergeTwoLists(ListNode a, ListNode b) {
        // A placeholder in front of the result, so the first append isn't a special case.
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        while (a != null && b != null) {
            // Take the smaller head. On a tie take from a, so equal values keep their order.
            if (a.val <= b.val) {
                tail.next = a;
                tail = a;
                a = a.next;
            } else {
                tail.next = b;
                tail = b;
                b = b.next;
            }
        }
        // One list ran out. The other is already sorted, so attach the rest of it whole.
        tail.next = a != null ? a : b;
        return dummy.next;
    }

    static ListNode buildList(int[] values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
        return head;
    }

    static String formatList(ListNode head) {
        List<String> parts = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) parts.add(String.valueOf(node.val));
        parts.add("null");
        return String.join(" -> ", parts);
    }

    public static void main(String[] args) {
        System.out.println(formatList(mergeTwoLists(buildList(new int[] {1, 2, 4}), buildList(new int[] {1, 3, 4})))); // 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> null
        System.out.println(formatList(mergeTwoLists(buildList(new int[] {}), buildList(new int[] {})))); // null
        System.out.println(formatList(mergeTwoLists(buildList(new int[] {}), buildList(new int[] {0})))); // 0 -> null
    }
}

from __future__ import annotations


class ListNode:
    """One node of a singly linked list."""

    def __init__(self, val: int, next: ListNode | None = None):
        self.val = val
        self.next = next


def has_cycle(head: ListNode | None) -> bool:
    """Whether following next pointers from head ever comes back to a node it has
    already passed. Floyd's fast and slow pointers use O(1) extra space."""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next  # One step. slow trails fast, so it isn't None here.
        fast = fast.next.next  # Two steps.
        # In a cycle, fast closes the gap by one node per step, so it can't skip slow.
        if slow is fast:
            return True
    return False  # fast reached the end, so there's no cycle.


def build_with_cycle(values: list[int], pos: int) -> ListNode | None:
    """Builds a list from values. If pos isn't -1, the tail links back to the node
    at index pos, which makes a cycle."""
    nodes = [ListNode(value) for value in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos >= 0:
        nodes[-1].next = nodes[pos]  # Close the loop.
    return nodes[0] if nodes else None


if __name__ == "__main__":
    print(has_cycle(build_with_cycle([3, 2, 0, -4], 1)))  # True
    print(has_cycle(build_with_cycle([1, 2], 0)))  # True
    print(has_cycle(build_with_cycle([1], -1)))  # False
    print(has_cycle(build_with_cycle([], -1)))  # False

// One node of a singly linked list.
export class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// Whether following next pointers from head ever comes back to a node it has
// already passed. Floyd's fast and slow pointers use O(1) extra space.
export function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next; // One step. slow trails fast, so it isn't null here.
    fast = fast.next.next; // Two steps.
    // In a cycle, fast closes the gap by one node per step, so it can't skip slow.
    if (slow === fast) return true;
  }
  return false; // fast reached the end, so there's no cycle.
}

// Builds a list from values. If pos isn't -1, the tail links back to the node
// at index pos, which makes a cycle.
function buildWithCycle(values: number[], pos: number): ListNode | null {
  const nodes = values.map((value) => new ListNode(value));
  for (let i = 0; i + 1 < nodes.length; i++) nodes[i].next = nodes[i + 1];
  if (pos >= 0) nodes[nodes.length - 1].next = nodes[pos]; // Close the loop.
  return nodes.length > 0 ? nodes[0] : null;
}

console.log(hasCycle(buildWithCycle([3, 2, 0, -4], 1))); // true
console.log(hasCycle(buildWithCycle([1, 2], 0))); // true
console.log(hasCycle(buildWithCycle([1], -1))); // false
console.log(hasCycle(buildWithCycle([], -1))); // false

package main

import "fmt"

// ListNode is one node of a singly linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// hasCycle reports whether following Next pointers from head ever comes back
// to a node it has already passed. Floyd's fast and slow pointers use O(1)
// extra space.
func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next      // One step. slow trails fast, so it isn't nil here.
		fast = fast.Next.Next // Two steps.
		// In a cycle, fast closes the gap by one node per step, so it can't skip slow.
		if slow == fast {
			return true
		}
	}
	return false // fast reached the end, so there's no cycle.
}

// buildWithCycle builds a list from values. If pos isn't -1, the tail links
// back to the node at index pos, which makes a cycle.
func buildWithCycle(values []int, pos int) *ListNode {
	nodes := make([]*ListNode, len(values))
	for i, value := range values {
		nodes[i] = &ListNode{Val: value}
	}
	for i := 0; i+1 < len(nodes); i++ {
		nodes[i].Next = nodes[i+1]
	}
	if pos >= 0 {
		nodes[len(nodes)-1].Next = nodes[pos] // Close the loop.
	}
	if len(nodes) == 0 {
		return nil
	}
	return nodes[0]
}

func main() {
	fmt.Println(hasCycle(buildWithCycle([]int{3, 2, 0, -4}, 1))) // true
	fmt.Println(hasCycle(buildWithCycle([]int{1, 2}, 0)))        // true
	fmt.Println(hasCycle(buildWithCycle([]int{1}, -1)))          // false
	fmt.Println(hasCycle(buildWithCycle([]int{}, -1)))           // false
}

using System;
using System.Linq;

public class Solution
{
    // One node of a singly linked list.
    public class ListNode
    {
        public int Val;
        public ListNode? Next;

        public ListNode(int val, ListNode? next = null)
        {
            Val = val;
            Next = next;
        }
    }

    // Whether following Next pointers from head ever comes back to a node it has
    // already passed. Floyd's fast and slow pointers use O(1) extra space.
    public static bool HasCycle(ListNode? head)
    {
        var slow = head;
        var fast = head;
        while (fast != null && fast.Next != null)
        {
            slow = slow!.Next; // One step. slow trails fast, so it isn't null here.
            fast = fast.Next.Next; // Two steps.
            // In a cycle, fast closes the gap by one node per step, so it can't skip slow.
            if (slow == fast) return true;
        }
        return false; // fast reached the end, so there's no cycle.
    }

    // Builds a list from values. If pos isn't -1, the tail links back to the node
    // at index pos, which makes a cycle.
    static ListNode? BuildWithCycle(int[] values, int pos)
    {
        var nodes = values.Select(value => new ListNode(value)).ToArray();
        for (int i = 0; i + 1 < nodes.Length; i++) nodes[i].Next = nodes[i + 1];
        if (pos >= 0) nodes[^1].Next = nodes[pos]; // Close the loop.
        return nodes.Length > 0 ? nodes[0] : null;
    }

    public static void Main()
    {
        Console.WriteLine(HasCycle(BuildWithCycle(new[] { 3, 2, 0, -4 }, 1))); // True
        Console.WriteLine(HasCycle(BuildWithCycle(new[] { 1, 2 }, 0))); // True
        Console.WriteLine(HasCycle(BuildWithCycle(new[] { 1 }, -1))); // False
        Console.WriteLine(HasCycle(BuildWithCycle(new int[0], -1))); // False
    }
}

public class Solution {
    // One node of a singly linked list.
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // Whether following next pointers from head ever comes back to a node it has
    // already passed. Floyd's fast and slow pointers use O(1) extra space.
    static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; // One step. slow trails fast, so it isn't null here.
            fast = fast.next.next; // Two steps.
            // In a cycle, fast closes the gap by one node per step, so it can't skip slow.
            if (slow == fast) return true;
        }
        return false; // fast reached the end, so there's no cycle.
    }

    // Builds a list from values. If pos isn't -1, the tail links back to the node
    // at index pos, which makes a cycle.
    static ListNode buildWithCycle(int[] values, int pos) {
        ListNode[] nodes = new ListNode[values.length];
        for (int i = 0; i < values.length; i++) nodes[i] = new ListNode(values[i], null);
        for (int i = 0; i + 1 < nodes.length; i++) nodes[i].next = nodes[i + 1];
        if (pos >= 0) nodes[nodes.length - 1].next = nodes[pos]; // Close the loop.
        return nodes.length > 0 ? nodes[0] : null;
    }

    public static void main(String[] args) {
        System.out.println(hasCycle(buildWithCycle(new int[] {3, 2, 0, -4}, 1))); // true
        System.out.println(hasCycle(buildWithCycle(new int[] {1, 2}, 0))); // true
        System.out.println(hasCycle(buildWithCycle(new int[] {1}, -1))); // false
        System.out.println(hasCycle(buildWithCycle(new int[] {}, -1))); // false
    }
}