A Collection Linked List Algorithms and questions

linked_list.go

package main

import (
	"container/list"
	"fmt"
)

// ListNode Definition
type ListNode struct {
	Val  int
	Next *ListNode
}

// 1. Add Two Numbers
func addTwoNumbers(l1, l2 *ListNode) {
	dummy := &ListNode{}
	curr := dummy
	carry := 0

	for l1 != nil || l2 != nil || carry > 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		curr.Next = &ListNode{Val: sum % 10}
		carry = sum / 10
		curr = curr.Next
	}

	printList(dummy.Next)
}

// 2. Reverse a Linked List
func reverseList(head *ListNode) {
	var prev *ListNode
	curr := head
	for curr != nil {
		nextTemp := curr.Next
		curr.Next = prev
		prev = curr
		curr = nextTemp
	}
	printList(prev)
}

// 3. Merge Two Sorted Lists
func mergeTwoLists(l1, l2 *ListNode) {
	dummy := &ListNode{}
	curr := dummy
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			curr.Next = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			l2 = l2.Next
		}
		curr = curr.Next
	}
	if l1 != nil {
		curr.Next = l1
	}
	if l2 != nil {
		curr.Next = l2
	}
	printList(dummy.Next)
}

// 4. Remove Nth Node from End of List
func removeNthFromEnd(head *ListNode, n int) {
	dummy := &ListNode{Next: head}
	first := dummy
	second := dummy

	for i := 0; i <= n; i++ {
		first = first.Next
	}

	for first != nil {
		first = first.Next
		second = second.Next
	}

	second.Next = second.Next.Next
	printList(dummy.Next)
}

// 5. Detect Cycle in a Linked List
func hasCycle(head *ListNode) {
	slow := head
	fast := head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			fmt.Println(true)
			return
		}
	}
	fmt.Println(false)
}

// 6. LRU Cache
type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type Pair struct {
	key, value int
}

func Constructor(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

func (lru *LRUCache) Get(key int) int {
	if node, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(node)
		return node.Value.(Pair).value
	}
	return -1
}

func (lru *LRUCache) Put(key int, value int) {
	if node, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(node)
		node.Value = Pair{key, value}
		return
	}
	if lru.list.Len() == lru.capacity {
		back := lru.list.Back()
		delete(lru.cache, back.Value.(Pair).key)
		lru.list.Remove(back)
	}
	node := lru.list.PushFront(Pair{key, value})
	lru.cache[key] = node
}

func testLRUCache() {
	lru := Constructor(2)
	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1)) // 1
	lru.Put(3, 3)
	fmt.Println(lru.Get(2)) // -1 (evicted)
	lru.Put(4, 4)
	fmt.Println(lru.Get(1)) // -1 (evicted)
	fmt.Println(lru.Get(3)) // 3
	fmt.Println(lru.Get(4)) // 4
}

// Utility to print a linked list
func printList(head *ListNode) {
	for head != nil {
		fmt.Print(head.Val)
		if head.Next != nil {
			fmt.Print(" -> ")
		}
		head = head.Next
	}
	fmt.Println()
}

// Helper to build list from slice
func buildList(nums []int) *ListNode {
	dummy := &ListNode{}
	curr := dummy
	for _, num := range nums {
		curr.Next = &ListNode{Val: num}
		curr = curr.Next
	}
	return dummy.Next
}

// Main function to test all
func main() {
	addTwoNumbers(buildList([]int{2, 4, 3}), buildList([]int{5, 6, 4})) // 7 -> 0 -> 8

	reverseList(buildList([]int{1, 2, 3, 4, 5})) // 5 -> 4 -> 3 -> 2 -> 1

	mergeTwoLists(buildList([]int{1, 2, 4}), buildList([]int{1, 3, 4})) // 1 -> 1 -> 2 -> 3 -> 4 -> 4

	removeNthFromEnd(buildList([]int{1, 2, 3, 4, 5}), 2) // 1 -> 2 -> 3 -> 5

	// Detect Cycle (build manually to form cycle)
	node1 := &ListNode{Val: 3}
	node2 := &ListNode{Val: 2}
	node3 := &ListNode{Val: 0}
	node4 := &ListNode{Val: -4}
	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node2 // cycle here
	hasCycle(node1)    // true

	// LRU Cache
	testLRUCache()
}