Reversing Linked Lists and Related Problems with Go Implementations

This document covers several classic linked‑list problems from LeetCode, providing problem statements, algorithmic insights, and full Go implementations.

1. Reverse the entire linked list

Problem: Reverse a singly‑linked list. Example input 1→2→3→4→5→NULL yields 5→4→3→2→1→NULL. The solution can be iterative or recursive.

Algorithm idea: Use two pointers, pre (previous node) and next (temporary storage for the next node). Iterate through the list, re‑link each node to its predecessor in four steps: backup next node, reverse the link, move pre forward, and advance the current node.

type LikedList struct{
    Val  int
    Next *LikedList
}

// Head insertion method to reverse a singly linked list
func reverseLikedList(head *LikedList) *LikedList {
    if head == nil || head.Next == nil {
        return head
    }
    var pre, next *LikedList
    for head != nil {
        next = head.Next          // backup next node
        head.Next = pre          // reverse link
        pre = head               // move pre forward
        head = next              // advance current node
    }
    return pre // pre now points to the new head
}

2. Reverse a sub‑list from position m to n

Problem: Given positions m and n (1 ≤ m ≤ n ≤ length), reverse the nodes between them in a single pass.

Algorithm idea: Record four critical nodes: the predecessor of m, the m‑th node, the n‑th node, and the successor of n. Move a pointer to the m‑th node, then iteratively reverse the next n‑m+1 nodes, finally reconnect the reversed segment with the surrounding parts.

/**
 * Definition for singly‑linked list.
 * type ListNode struct {
 *     Val  int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    changeLen := n - m + 1
    var pre *ListNode = nil
    var result *ListNode = head
    move := m - 1
    for head != nil && move > 0 {
        pre = head
        head = head.Next
        move--
    }
    var reversedListTail *ListNode = head
    var reversedListHead *ListNode = nil
    for head != nil && changeLen > 0 {
        next := head.Next
        head.Next = reversedListHead
        reversedListHead = head
        head = next
        changeLen--
    }
    reversedListTail.Next = head
    if pre != nil {
        pre.Next = reversedListHead
    } else {
        result = reversedListHead
    }
    return result
}

3. Find the intersection node of two singly linked lists

Problem: Return the first common node of two lists, or null if they do not intersect. The solution should run in O(n) time and O(1) extra space.

Algorithm idea: Compute the lengths of both lists, advance the head of the longer list by the length difference, then move both heads together until they meet or reach the end.

/**
 * Definition for singly‑linked list.
 * type ListNode struct {
 *     Val  int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var lenA, lenB int
    lenA = getListLength(headA)
    lenB = getListLength(headB)
    if lenA > lenB {
        headA = forwardDeltaLenNode(lenA, lenB, headA)
    } else {
        headB = forwardDeltaLenNode(lenB, lenA, headB)
    }
    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

func getListLength(head *ListNode) int {
    var length int
    for head != nil {
        length++
        head = head.Next
    }
    return length
}

func forwardDeltaLenNode(longLen, shortLen int, longList *ListNode) *ListNode {
    delta := longLen - shortLen
    for longList != nil && delta != 0 {
        longList = longList.Next
        delta--
    }
    return longList
}

4. Detect a cycle in a linked list and locate its start and length

The article outlines the problem statement (detect whether a list contains a loop, and if so, return the entry node and the loop length) but does not provide concrete code; typical solutions use Floyd’s Tortoise‑and‑Hare algorithm.

5. Partition a linked list around a value x

Problem: Rearrange the list so that all nodes with values less than x appear before nodes with values greater than or equal to x, preserving the original relative order within each partition.

Algorithm idea: Create two dummy heads ( preHead and postHead) for the “less” and “greater/equal” partitions. Iterate through the original list, appending each node to the appropriate partition, then link the two partitions together.

/**
 * Definition for singly‑linked list.
 * type ListNode struct {
 *     Val  int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    preHead := &ListNode{0, nil}
    postHead := &ListNode{0, nil}
    prePtr := preHead
    postPtr := postHead
    for head != nil {
        if head.Val < x {
            prePtr.Next = head
            prePtr = head
        } else {
            postPtr.Next = head
            postPtr = head
        }
        head = head.Next
    }
    prePtr.Next = postHead.Next
    postPtr.Next = nil
    return preHead.Next
}

All the above solutions are written in Go and are intended for interview preparation on platforms such as LeetCode.

Source: goline.blog.csdn.net article (original Chinese content).