链表基础概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。与数组不同，链表在内存中非连续存储，通过指针实现逻辑上的顺序连接。

常见类型：

• 单链表：每个节点指向下一个节点，尾节点指向 NULL。
• 双链表：节点包含前驱和后继指针，支持双向遍历。
• 循环链表：尾节点指向头节点，形成闭环。

链表核心操作

插入与删除

• 插入：修改相邻节点的指针，时间复杂度通常为 $O(1)$（已知前驱节点）。
• 删除：调整指针跳过目标节点，注意处理头尾节点边界。

遍历与搜索

• 遍历：从头节点出发，依次访问每个节点直至 NULL。
• 搜索：线性查找，时间复杂度 $O(n)$。

求职应用场景

高频面试题

1. 反转链表：通过迭代或递归实现指针方向反转。
2. 检测环：快慢指针法（Floyd's Cycle Algorithm）。
3. 合并有序链表：双指针比较节点值，逐步合并。
4. 删除倒数第N个节点：快慢指针定位目标前驱。

实际应用

• 内存管理中的动态分配（如操作系统内核）。
• LRU缓存淘汰算法（结合哈希表实现）。
• 图的邻接表表示。

算法示例（golang）

   1. 题目：

           给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤10000≤n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时，
        经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

                               

解题思路：

双链表法

原链表  1->2->3->nil
新链表  nil


第一次:   1->2->3->nil
          1->nil

第二次:   1->2->3->nil
          2->1->nil

第三次:   1->2->3->nil
          3->2->1->nil

具体代码：

func ReverseList(head *ListNode) *ListNode {
	//首先判断链表是否为空
	if head == nil {
		return head
	}
	var newHead *ListNode = nil // 你口中的“新链表”
	for head != nil {           // head 是原链表头
		next := head.Next   // 先保存原链下一个节点
		head.Next = newHead // 头插到新链表
		newHead = head      // 新链表头更新
		head = next         // 原链表头后移
	}
	return newHead
}

题目：

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL, m=2,n=4,
返回               1→4→3→2→5→NULL.

解题思路：

可以看出这道题的解题思路是和上面那道题类似
我们需要找到m,n的位置然后将这段链表反转

具体代码：

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	// write code here
	//首先判断链表是否为空和m和n是否相等
	if head == nil || m == n {
		return head
	}


	// 虚拟头节点，仅用于统一边界情况，不复制数据
	dummy := &ListNode{Next: head}
	prev := dummy
	//将prev移动到m-1的位置
	for i := 0; i < m-1; i++ {
		prev = prev.Next
	}
	//开始反转的部分的头节点
	start := prev.Next
	then := start.Next

	// 反转从第 m 个节点到第 n 个节点的部分
	for i := m; i < n; i++ {
		start.Next = then.Next
		then.Next = prev.Next
		prev.Next = then
		then = start.Next
	}
    return dummy.Next
}

题目

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
给定的链表是               1→2→3→4→5
对于 k=2 , 你应该返回 2→1→4→3→5
对于 k=3 , 你应该返回 3→2→1→4→5

解题思路

先判断给出的信息能不能完成要做的操作
再使用头插法分块完成链表反转
最后在递归

具体代码

func reverseKGroup(head *ListNode, k int) *ListNode {
	if k <= 1 || head == nil {
		return head
	}
	// 先测这一段够不够 k 个
	tail := head
	for i := 0; i < k; i++ {
		if tail == nil { // 不足 k 个，直接返回
			return head
		}
		tail = tail.Next
	}

	// 反转这 k 个：用头插法
	var prev *ListNode = nil
	curr := head
	for i := 0; i < k; i++ {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
    
	// 此时 prev 是这一组的新头，curr 是下一组的头
	// 递归处理后面，并把反转后的尾（原来的 head）连上去
	head.Next = reverseKGroup(curr, k)
	return prev
}

迭代法
func reverseKGroup(head *ListNode, k int) *ListNode {
    if k <= 1 {
        return head
    }
    dummy := &ListNode{Next: head}
    groupPrev := dummy               // 上一组的尾巴

    for {
        kth := groupPrev
        // 数 k 步，看本组够不够
        for i := 0; i < k && kth != nil; i++ {
            kth = kth.Next
        }
        if kth == nil {              // 不足 k 个，收工
            break
        }
        groupNext := kth.Next        // 记下下一组的头
        prev, curr := groupPrev.Next, groupPrev.Next.Next

        // 头插法反转本组（k-1 次即可）
        for i := 0; i < k-1; i++ {
            next := curr.Next
            curr.Next = prev
            prev = curr
            curr = next
        }
        // 把反转后的段落重新接回去
        tail := groupPrev.Next       // 原来的头，现在是尾
        tail.Next = groupNext
        groupPrev.Next = kth         // kth 现在是新头
        groupPrev = tail             // 继续下一组
    }
    return dummy.Next
}

学习建议

• 手写练习：手动模拟指针变化过程，加深理解。
• 复杂度分析：明确各操作的时间与空间复杂度。
• 题目拓展：尝试LeetCode题库（如 #206、#141、#21）。

链表是算法面试的基石，掌握其原理和变体对求职至关重要。