Linked Lists

// Package linkedlist is Module 3: singly linked lists.
//
// Go's standard library has container/list (a doubly linked list), but you
// rarely want it in practice — slices win on cache locality. Linked lists
// are here because they teach pointer manipulation, which trees and graphs
// build on.
package linkedlist

// Node is one element of a singly linked chain.
type Node[T any] struct {
	Val  T
	Next *Node[T]
}

// LinkedList keeps a head and tail pointer so both ends are O(1) to append to.
// Invariants your methods must keep:
//   - size == number of nodes reachable from head
//   - tail is the last node (tail.Next == nil), or nil when the list is empty
type LinkedList[T comparable] struct {
	head *Node[T]
	tail *Node[T]
	size int
}

// Len returns the number of elements.
func (l *LinkedList[T]) Len() int { return l.size }

// Values returns the elements from head to tail.
func (l *LinkedList[T]) Values() []T { return ToSlice(l.head) }

// FromSlice builds a chain of nodes and returns its head (nil for empty).
func FromSlice[T any](vals []T) *Node[T] {
	var head, tail *Node[T]
	for _, v := range vals {
		n := &Node[T]{Val: v}
		if head == nil {
			head = n
		} else {
			tail.Next = n
		}
		tail = n
	}
	return head
}

// ToSlice walks a chain from head. It stops after 10,000 nodes so an
// accidental cycle shows up as a wrong answer instead of a hung test.
func ToSlice[T any](head *Node[T]) []T {
	var out []T
	for n := head; n != nil && len(out) < 10_000; n = n.Next {
		out = append(out, n.Val)
	}
	return out
}

package linkedlist

import (
	"slices"
	"testing"
)

func checkInvariants[T comparable](t *testing.T, l *LinkedList[T]) {
	t.Helper()
	n := len(l.Values())
	if n != l.size {
		t.Errorf("size = %d but %d nodes are reachable from head", l.size, n)
	}
	if (l.head == nil) != (l.tail == nil) {
		t.Errorf("head and tail must be nil together (head nil: %v, tail nil: %v)", l.head == nil, l.tail == nil)
	}
	if l.tail != nil && l.tail.Next != nil {
		t.Error("tail.Next should be nil")
	}
	if l.head != nil {
		last := l.head
		for last.Next != nil {
			last = last.Next
		}
		if last != l.tail {
			t.Error("tail does not point at the last node")
		}
	}
}

func TestPushAndPop(t *testing.T) {
	var l LinkedList[int]
	l.PushBack(2)
	l.PushBack(3)
	l.PushFront(1)
	if got, want := l.Values(), []int{1, 2, 3}; !slices.Equal(got, want) {
		t.Fatalf("Values() = %v, want %v", got, want)
	}
	checkInvariants(t, &l)
	for _, want := range []int{1, 2, 3} {
		if v, ok := l.PopFront(); !ok || v != want {
			t.Fatalf("PopFront() = (%d, %v), want (%d, true)", v, ok, want)
		}
		checkInvariants(t, &l)
	}
	if _, ok := l.PopFront(); ok {
		t.Error("PopFront() on empty list should return ok=false")
	}
	l.PushBack(9) // tail must have been reset for this to work
	if got := l.Values(); !slices.Equal(got, []int{9}) {
		t.Errorf("after emptying and PushBack(9): %v, want [9]", got)
	}
	checkInvariants(t, &l)
}

func TestContainsRemove(t *testing.T) {
	var l LinkedList[string]
	for _, s := range []string{"a", "b", "c", "d"} {
		l.PushBack(s)
	}
	if !l.Contains("c") || l.Contains("z") {
		t.Fatal("Contains gave the wrong answer")
	}
	steps := []struct {
		remove string
		ok     bool
		want   []string
	}{
		{"a", true, []string{"b", "c", "d"}}, // head
		{"d", true, []string{"b", "c"}},      // tail
		{"x", false, []string{"b", "c"}},     // missing
		{"b", true, []string{"c"}},
		{"c", true, nil}, // only node
	}
	for _, s := range steps {
		if ok := l.Remove(s.remove); ok != s.ok {
			t.Fatalf("Remove(%q) = %v, want %v", s.remove, ok, s.ok)
		}
		if got := l.Values(); !slices.Equal(got, s.want) {
			t.Fatalf("after Remove(%q): %v, want %v", s.remove, got, s.want)
		}
		checkInvariants(t, &l)
	}
	l.PushBack("z")
	if got := l.Values(); !slices.Equal(got, []string{"z"}) {
		t.Errorf("PushBack after removing everything: %v, want [z]", got)
	}
}

func TestReverse(t *testing.T) {
	for _, in := range [][]int{{1, 2, 3, 4, 5}, {1, 2}, {1}, nil} {
		want := slices.Clone(in)
		slices.Reverse(want)
		if got := ToSlice(Reverse(FromSlice(in))); !slices.Equal(got, want) {
			t.Errorf("Reverse(%v) = %v, want %v", in, got, want)
		}
	}
}

func TestMiddle(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		want int
	}{
		{[]int{1, 2, 3, 4, 5}, 3},
		{[]int{1, 2, 3, 4}, 3},
		{[]int{1}, 1},
	} {
		m := Middle(FromSlice(tc.in))
		if m == nil || m.Val != tc.want {
			t.Errorf("Middle(%v) = %v, want node %d", tc.in, m, tc.want)
		}
	}
	if Middle[int](nil) != nil {
		t.Error("Middle(nil) should be nil")
	}
}

func TestHasCycle(t *testing.T) {
	head := FromSlice([]int{1, 2, 3, 4, 5})
	if HasCycle(head) {
		t.Error("straight list reported as a cycle")
	}
	tail := head
	for tail.Next != nil {
		tail = tail.Next
	}
	tail.Next = head.Next.Next // 5 -> 3
	if !HasCycle(head) {
		t.Error("cycle 5->3 not detected")
	}
	self := &Node[int]{Val: 1}
	self.Next = self
	if !HasCycle(self) {
		t.Error("self-loop not detected")
	}
	if HasCycle[int](nil) {
		t.Error("nil list reported as a cycle")
	}
}

func TestMergeSorted(t *testing.T) {
	for _, tc := range []struct{ a, b, want []int }{
		{[]int{1, 3, 5}, []int{2, 4, 6}, []int{1, 2, 3, 4, 5, 6}},
		{[]int{1, 1, 9}, []int{1, 2}, []int{1, 1, 1, 2, 9}},
		{nil, []int{4}, []int{4}},
		{[]int{0}, nil, []int{0}},
		{nil, nil, nil},
	} {
		if got := ToSlice(MergeSorted(FromSlice(tc.a), FromSlice(tc.b))); !slices.Equal(got, tc.want) {
			t.Errorf("MergeSorted(%v, %v) = %v, want %v", tc.a, tc.b, got, tc.want)
		}
	}
}

func TestRemoveNthFromEnd(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		n    int
		want []int
	}{
		{[]int{1, 2, 3, 4, 5}, 2, []int{1, 2, 3, 5}},
		{[]int{1, 2, 3, 4, 5}, 5, []int{2, 3, 4, 5}},
		{[]int{1, 2, 3, 4, 5}, 1, []int{1, 2, 3, 4}},
		{[]int{1}, 1, nil},
		{[]int{1, 2}, 3, []int{1, 2}},
	} {
		if got := ToSlice(RemoveNthFromEnd(FromSlice(tc.in), tc.n)); !slices.Equal(got, tc.want) {
			t.Errorf("RemoveNthFromEnd(%v, %d) = %v, want %v", tc.in, tc.n, got, tc.want)
		}
	}
}

//go:build solutions

package linkedlist

import "cmp"

func (l *LinkedList[T]) PushFront(v T) {
	n := &Node[T]{Val: v, Next: l.head}
	l.head = n
	if l.tail == nil {
		l.tail = n
	}
	l.size++
}

func (l *LinkedList[T]) PushBack(v T) {
	n := &Node[T]{Val: v}
	if l.tail == nil {
		l.head, l.tail = n, n
	} else {
		l.tail.Next = n
		l.tail = n
	}
	l.size++
}

func (l *LinkedList[T]) PopFront() (T, bool) {
	var zero T
	if l.head == nil {
		return zero, false
	}
	n := l.head
	l.head = n.Next
	if l.head == nil {
		l.tail = nil
	}
	l.size--
	return n.Val, true
}

func (l *LinkedList[T]) Contains(v T) bool {
	for n := l.head; n != nil; n = n.Next {
		if n.Val == v {
			return true
		}
	}
	return false
}

func (l *LinkedList[T]) Remove(v T) bool {
	// A dummy node in front of head removes the "is it the head?" special case.
	dummy := &Node[T]{Next: l.head}
	for prev := dummy; prev.Next != nil; prev = prev.Next {
		if prev.Next.Val == v {
			if prev.Next == l.tail {
				l.tail = prev
			}
			prev.Next = prev.Next.Next
			l.head = dummy.Next
			if l.head == nil {
				l.tail = nil
			}
			l.size--
			return true
		}
	}
	return false
}

func Reverse[T any](head *Node[T]) *Node[T] {
	var prev *Node[T]
	for cur := head; cur != nil; {
		next := cur.Next
		cur.Next = prev
		prev, cur = cur, next
	}
	return prev
}

func Middle[T any](head *Node[T]) *Node[T] {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func HasCycle[T any](head *Node[T]) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

func MergeSorted[T cmp.Ordered](a, b *Node[T]) *Node[T] {
	dummy := &Node[T]{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

func RemoveNthFromEnd[T any](head *Node[T], n int) *Node[T] {
	dummy := &Node[T]{Next: head}
	lead := dummy
	for i := 0; i < n; i++ {
		if lead.Next == nil {
			return head // n is larger than the list
		}
		lead = lead.Next
	}
	trail := dummy
	for lead.Next != nil {
		lead, trail = lead.Next, trail.Next
	}
	trail.Next = trail.Next.Next
	return dummy.Next
}