Interview Gym PRO

Linked List

A linked list is a chain of nodes where each node points to the next one — like a scavenger hunt where every clue tells you where the next one is. There is no index access, so the skill is rewiring pointers without losing the rest of the chain.

After this topic: You can reverse, merge and split lists, use fast/slow pointers, and use a dummy node to remove edge cases.

Do these first: Two Pointers

0 of 11 solved0%

Step 1 · Read the lesson

Linked List · Fast & Slow Pointers

Rewire pointers carefully; use a fast and slow pointer to find cycles and middles.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Reverse Linked ListEasy
Before you flip a node's pointer, what must you save so you do not lose the rest of the list?
Keep prev (nil) and curr; in a loop save next, point curr.next at prev, then advance both.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func reverseList(head *ListNode) *ListNode
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Linked List · Fast & Slow Pointers lesson page.
// ReverseList: flip every Next pointer in place. func ReverseList(head *ListNode) *ListNode { var prev *ListNode for cur := head; cur != nil; { next := cur.Next // save it, or we lose the rest of the list cur.Next = prev // flip the arrow prev, cur = cur, next } return prev }

2.Merge Two Sorted ListsEasy

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Linked List · Fast & Slow Pointers lesson page.

// MergeTwoLists: splice two sorted lists into one.
// The dummy node removes the "which node is the head?" special case.
func MergeTwoLists(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val { // <= keeps the merge stable
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a // at most one list has leftovers: attach it whole
	} else {
		tail.Next = b
	}
	return dummy.Next
}

3.Linked List CycleEasy
Two runners on a circular track at different speeds will eventually meet.
Slow moves 1 step, fast moves 2. If fast reaches nil there is no cycle; if they ever meet there is one.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func hasCycle(head *ListNode) bool
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Linked List · Fast & Slow Pointers lesson page.
// HasCycle: Floyd's tortoise and hare. func HasCycle(head *ListNode) bool { slow, fast := head, head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next if slow == fast { // compare nodes (pointers), never values return true } } return false }

4.Reorder ListMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func reorderList(head *ListNode)

Tested with go test. Try it yourself first, then compare.

// ReorderList turns L0→L1→…→Ln into L0→Ln→L1→Ln-1→… in place, in three small steps:
// find the middle, reverse the second half, then weave the two halves together.
func ReorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	slow, fast := head, head.Next // fast starts one ahead so slow stops at the END of the first half
	for fast != nil && fast.Next != nil {
		slow, fast = slow.Next, fast.Next.Next
	}
	second := slow.Next
	slow.Next = nil // cut the list in two
	var prev *ListNode
	for second != nil {
		second.Next, prev, second = prev, second, second.Next // reverse the second half
	}
	first, second := head, prev
	for second != nil {
		fNext, sNext := first.Next, second.Next
		first.Next = second
		second.Next = fNext
		first, second = fNext, sNext
	}
}

5.Remove Nth Node From End of ListMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func removeNthFromEnd(head *ListNode, n int) *ListNode

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Linked List · Fast & Slow Pointers lesson page.

// RemoveNthFromEnd: remove the nth node from the end in one pass.
// fast gets an n-step head start, so when fast reaches the end, slow is just before the target.
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head} // lets us delete the real head without a special case
	fast, slow := dummy, dummy
	for i := 0; i < n && fast != nil; i++ {
		fast = fast.Next
	}
	if fast == nil { // n is larger than the list: nothing to remove
		return head
	}
	for fast.Next != nil {
		fast, slow = fast.Next, slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}

6.Copy List with Random PointerMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func copyRandomList(head *Node) *Node

Tested with go test. Try it yourself first, then compare.

// RandomNode is a list node with an extra pointer to any node in the list (or nil).
type RandomNode struct {
	Val          int
	Next, Random *RandomNode
}

// CopyRandomList makes a deep copy. First pass: create one copy per original and remember original→copy
// in a map. Second pass: wire the copies' Next and Random through that map.
func CopyRandomList(head *RandomNode) *RandomNode {
	copies := map[*RandomNode]*RandomNode{nil: nil} // nil maps to nil so end-of-list needs no special case
	for n := head; n != nil; n = n.Next {
		copies[n] = &RandomNode{Val: n.Val}
	}
	for n := head; n != nil; n = n.Next {
		copies[n].Next = copies[n.Next]
		copies[n].Random = copies[n.Random]
	}
	return copies[head]
}

7.Add Two NumbersMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode

Tested with go test. Try it yourself first, then compare.

// AddTwoNumbers adds two numbers stored as reversed digit lists, exactly like adding on paper:
// add the digits plus the carry, keep the last digit, carry the rest.
func AddTwoNumbers(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := 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
		}
		tail.Next = &ListNode{Val: sum % 10}
		tail = tail.Next
		carry = sum / 10
	}
	return dummy.Next
}

8.Find the Duplicate NumberMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func findDuplicate(nums []int) int

Tested with go test. Try it yourself first, then compare.

// FindDuplicate: n+1 numbers in 1..n. Treat each value as a pointer to the index with that number; two
// indexes pointing at the same place means a cycle, and the cycle's entrance is the duplicate (Floyd).
func FindDuplicate(nums []int) int {
	slow, fast := nums[0], nums[nums[0]]
	for slow != fast {
		slow = nums[slow]
		fast = nums[nums[fast]]
	}
	slow = 0 // distance to the cycle entrance is equal from the start and from the meeting point
	for slow != fast {
		slow = nums[slow]
		fast = nums[fast]
	}
	return slow
}

9.LRU CacheMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

type LRUCache struct{}
func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Tested with go test. Try it yourself first, then compare.

// LRUCache evicts the least recently used key. A hash map finds a key in O(1); a doubly linked list keeps
// keys in recency order (front = most recent) so moving or removing a node is O(1) too.
type LRUCache struct {
	cap        int
	nodes      map[int]*lruNode
	head, tail *lruNode // sentinels: head.next is the most recent, tail.prev the least recent
}
type lruNode struct {
	key, val   int
	prev, next *lruNode
}

func NewLRUCache(capacity int) *LRUCache {
	c := &LRUCache{cap: capacity, nodes: map[int]*lruNode{}, head: &lruNode{}, tail: &lruNode{}}
	c.head.next, c.tail.prev = c.tail, c.head
	return c
}

func (c *LRUCache) remove(n *lruNode) { n.prev.next, n.next.prev = n.next, n.prev }
func (c *LRUCache) pushFront(n *lruNode) {
	n.next, n.prev = c.head.next, c.head
	c.head.next.prev = n
	c.head.next = n
}

func (c *LRUCache) Get(key int) int {
	n, ok := c.nodes[key]
	if !ok {
		return -1
	}
	c.remove(n)
	c.pushFront(n) // using a key makes it the most recent
	return n.val
}

func (c *LRUCache) Put(key, val int) {
	if n, ok := c.nodes[key]; ok {
		n.val = val
		c.remove(n)
		c.pushFront(n)
		return
	}
	if len(c.nodes) == c.cap {
		lru := c.tail.prev
		c.remove(lru)
		delete(c.nodes, lru.key)
	}
	n := &lruNode{key: key, val: val}
	c.nodes[key] = n
	c.pushFront(n)
}

10.Merge k Sorted ListsHard

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func mergeKLists(lists []*ListNode) *ListNode

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Linked List · Fast & Slow Pointers lesson page.

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

type nodeHeap []*ListNode

func (h nodeHeap) Len() int           { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x any)        { *h = append(*h, x.(*ListNode)) }
func (h *nodeHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// MergeKLists: the heap always holds the current head of every list;
// pop the smallest, append it, and push that node's successor.
func MergeKLists(lists []*ListNode) *ListNode {
	h := &nodeHeap{}
	for _, l := range lists {
		if l != nil {
			heap.Push(h, l)
		}
	}
	dummy := &ListNode{}
	tail := dummy
	for h.Len() > 0 {
		n := heap.Pop(h).(*ListNode)
		tail.Next = n
		tail = n
		if n.Next != nil {
			heap.Push(h, n.Next)
		}
	}
	return dummy.Next
}

11.Reverse Nodes in k-GroupHard

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func reverseKGroup(head *ListNode, k int) *ListNode

Tested with go test. Try it yourself first, then compare.

// ReverseKGroup reverses the list k nodes at a time; a final group shorter than k stays as it is.
func ReverseKGroup(head *ListNode, k int) *ListNode {
	dummy := &ListNode{Next: head}
	groupPrev := dummy
	for {
		kth := groupPrev
		for i := 0; i < k && kth != nil; i++ {
			kth = kth.Next
		}
		if kth == nil {
			return dummy.Next // fewer than k nodes left
		}
		groupNext := kth.Next
		prev, cur := groupNext, groupPrev.Next // reversing toward groupNext reconnects the group to the rest
		for cur != groupNext {
			cur.Next, prev, cur = prev, cur, cur.Next
		}
		oldFirst := groupPrev.Next // the old first node is now the group's tail
		groupPrev.Next = kth
		groupPrev = oldFirst
	}
}

Step 3 · What this unlocks

Trees