Linked list manipulation is about rewiring pointers. Reversing a list is the fundamental operation — most other linked list problems build on it.
Use when: you need to reverse order, find the middle, detect cycles, or merge sorted lists.
In Go, we define a linked list node as a struct with a pointer to the next node.
Reverse iteratively by maintaining three pointers: prev, current, and next. At each step, rewire current to point backwards.
Save the next node before we overwrite the pointer.
Reverse the link: point current backwards.
Advance both pointers forward.
prev is now the new head.
Detect if a linked list has a cycle using Floyd’s tortoise and hare algorithm: slow moves 1 step, fast moves 2. If they meet, there’s a cycle.
Helper to build a list from a slice.
Helper to print a list.
Trace: 1 -> 2 -> 3 -> nil
Step 1: prev=nil, curr=1 -> curr.Next=nil, prev=1, curr=2 Step 2: prev=1, curr=2 -> curr.Next=1, prev=2, curr=3 Step 3: prev=2, curr=3 -> curr.Next=2, prev=3, curr=nil Result: 3 -> 2 -> 1 -> nil
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil { next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
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 {
return true
}
}
return false
}
func buildList(vals []int) *ListNode {
dummy := &ListNode{}
curr := dummy
for _, v := range vals {
curr.Next = &ListNode{Val: v}
curr = curr.Next
}
return dummy.Next
}
func printList(head *ListNode) {
for head != nil {
fmt.Printf("%d", head.Val)
if head.Next != nil {
fmt.Print(" -> ")
}
head = head.Next
}
fmt.Println()
}
func main() {
list := buildList([]int{1, 2, 3, 4, 5})
printList(list)
reversed := reverseList(list)
printList(reversed)
fmt.Println(hasCycle(buildList([]int{1, 2, 3})))
}