1.【Android程序员算法修炼】- 链表（上）

随着移动开发从‘增量时代’进入‘深耕时代’，企业对 Android 开发者的要求早已超越‘能实现功能’的层面。当用户对 App 的流畅度、响应速度提出更高要求，当内存优化、并发处理成为核心竞争力，算法能力就成了区分‘普通开发者’与‘资深工程师’的关键标尺。

本文将以牛客网的算法题为例，聚焦 Android 面试中高频出现的算法场景，从解题思路到代码实现，拆解那些让无数开发者‘卡壳’的经典问题。

1.【Android程序员算法修炼】- 链表（上）

2.【Android程序员算法修炼】- 链表（下）

3.【Android程序员算法修炼】二分查找、排序

4.【Android程序员算法修炼】二叉树（上）

5.【Android程序员算法修炼】二叉树（下）

6.【Android程序员算法修炼】堆、栈、队列

7.【Android程序员算法修炼】哈希

8.【Android程序员算法修炼】递归、回溯

9.【Android程序员算法修炼】动态规划（上）

10.【Android程序员算法修炼】动态规划（下）

11.【Android程序员算法修炼】字符串

12.【Android程序员算法修炼】双指针

13.【Android程序员算法修炼】贪心、模拟

链表概念

链表是一种线性数据结构，由一系列节点（Node）组成，每个节点包含两部分：

• 数据域：存储具体的数据（如整数、对象等）
• 指针域：存储下一个节点的地址（单链表），或同时存储上一个和下一个节点的地址（双向链表）

节点通过指针 “链式” 连接，形成一个序列，不需要连续的内存空间，这是它与数组的核心区别。

 public class ListNode {
   int val; // 数据域
   ListNode next = null; // 指针域
   public ListNode(int val) {
     this.val = val;
   }
}

链表的特点

1. 内存灵活：节点可以分散存储在内存中，通过指针关联，无需预先分配固定大小的连续空间

2. 操作特性：

   1. 插入 / 删除节点：只需修改指针指向（O (1)，已知前驱节点时）
   2. 访问节点：必须从头部开始遍历（O (n)，无法像数组那样通过索引直接访问）

3. 无固定容量限制：理论上只要内存足够，可无限扩展

常用解题技巧

链表算法题的解题技巧，核心围绕指针操作和链表特性展开，掌握这些技巧能高效解决80%以上的基础链表问题。以下是高频实用技巧：

1. 虚拟节点，又称哑节点（Dummy Node）

   1. 适用场景：处理头节点可能被修改的情况（如删除头节点、在头部插入）。
   2. 原理：创建一个虚拟节点（dummy），其next指向真正的头节点，统一操作逻辑，避免单独头节点为空的边界判断。

2. 双指针（快慢指针）

   1. 适用场景：找中间节点、判断环、环入口、倒数第k个节点。

   2. 用法：

      • 中间节点：快指针每次走2步，慢指针每次走1步，快指针到尾时，慢指针在中间。
      • 环检测：若快慢指针相遇，则有环；否则无环（LeetCode 141）。
      • 倒数第k个节点：快指针先走k步，再和慢指针一起走，快指针到尾时，慢指针即目标（LeetCode 19）。

3. 多指针追踪

   1. 适用场景：反转链表、复杂节点交换（如两两交换）。

经典例题

1. 反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为 n，反转该链表后，返回新链表的表头。

如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

数据范围： 0 ≤ n ≤ 10000 ≤ n ≤ 1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

解题思路

反转单链表的核心是改变节点之间的指针方向，将原本 “从前往后” 的指向改为 “从后往前”。由于要求空间复杂度 O (1)，不能创建新链表，需通过指针操作就地反转。

关键思路：

1. 使用 3 个指针追踪节点：prev（前一个节点，初始为 null）、curr（当前节点，初始为头节点）、nextTemp（临时保存下一个节点）。
2. 遍历链表时，依次将当前节点的next指向prev，完成局部反转。
3. 移动指针继续处理下一个节点，直到遍历结束，此时prev即为新的头节点。

/**
 * 定义链表节点
 */
 public class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val) {
     this.val = val;
   }
}

public class ReverseList {
    /**
     * 反转单链表
     * @param pHead 原链表头节点
     * @return 反转后新链表的头节点
     */
    public ListNode ReverseList(ListNode pHead) {
        // 边界条件：空链表或只有一个节点，直接返回原头节点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode prev = null;    // 前一个节点
        ListNode curr = pHead;   // 当前节点
        ListNode nextTemp = null;// 临时保存下一个节点

        while (curr != null) {
            nextTemp = curr.next; // 保存下一个节点，防止断链
            curr.next = prev;     // 反转当前节点的指针
            prev = curr;          // 移动prev到当前节点
            curr = nextTemp;      // 移动curr到下一个节点
        }

        // 循环结束后，prev即为新的头节点
        return prev;
    }
}

1. 合并两个有序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

数据范围： 0 ≤ n ≤ 1000，−1000 ≤ 节点值 ≤ 1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

示例1：

输入：{1,3,5},{2,4,6} 
返回值：{1,2,3,4,5,6}

示例2：

输入：{},{} 
返回值：{}

示例3：

输入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}

解题思路

合并两个递增排序的链表，核心是比较两个链表的节点值，按从小到大的顺序依次拼接，形成一个新的递增链表。由于输入链表已排序，可采用双指针法高效合并，避免额外排序操作。

关键思路：

1. 使用两个指针分别遍历两个输入链表（p1 对应链表 1，p2 对应链表 2）。
2. 创建一个哑节点（dummy）作为新链表的起始点，简化头节点处理。
3. 用一个指针（curr）构建新链表，每次比较 p1 和 p2 的值，将较小的节点接入新链表，并移动对应指针。
4. 当一个链表遍历结束后，将另一个链表的剩余节点直接接入新链表尾部。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int x) {
        val = x;
    }
}

public class MergeTwoLists {
    /**
     * 合并两个递增排序的链表
     * @param l1 第一个递增链表
     * @param l2 第二个递增链表
     * @return 合并后的递增链表头节点
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建哑节点，简化头节点处理
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy; // 用于构建新链表的指针

        // 双指针遍历两个链表，比较并拼接节点
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1; // 接入l1的当前节点
                l1 = l1.next;   // 移动l1指针
            } else {
                curr.next = l2; // 接入l2的当前节点
                l2 = l2.next;   // 移动l2指针
            }
            curr = curr.next; // 移动curr指针
        }

        // 拼接剩余节点（其中一个链表已遍历完）
        curr.next = (l1 != null) ? l1 : l2;

        // 哑节点的next即为合并后链表的头节点
        return dummy.next;
    }
}

1. 判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

数据范围：链表长度 0 ≤ n ≤ 10000，链表中任意节点的值满足 ∣val∣<=100000

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例1：

输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true

示例2：

输入：{1},-1
返回值：false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

示例3：

输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值：true

解题思路

判断链表是否有环，核心是检测指针是否会无限循环。最经典且高效的方法是快慢指针法（龟兔赛跑算法）：

1. 原理：设置两个指针，慢指针（slow）每次走 1 步，快指针（fast）每次走 2 步。

   1. 若链表无环：快指针会先到达链表尾部（指向 null），此时可判断无环。
   2. 若链表有环：快指针会在环内追上慢指针（两者相遇），此时可判断有环。

2. 优势：时间复杂度 O (n)（最多遍历 2n 次），空间复杂度 O (1)（仅用两个指针），无需额外存储节点，符合高效要求。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class HasCycle {
    /**
     * 判断链表是否有环
     * @param head 链表头节点
     * @return 有环返回true，否则返回false
     */
    public boolean hasCycle(ListNode head) {
        // 边界条件：空链表或单节点无环
        if (head == null || head.next == null) {
            return false;
        }

        // 初始化快慢指针
        ListNode slow = head;   // 慢指针，每次走1步
        ListNode fast = head;   // 快指针，每次走2步

        // 循环检测：快指针未到达尾部时继续
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走1步
            fast = fast.next.next;  // 快指针走2步

            // 快慢指针相遇，说明有环
            if (slow == fast) {
                return true;
            }
        }

        // 快指针到达尾部，无环
        return false;
    }
}

1. 链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 a(i) ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1：

输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

示例2：

输入：{2},8
返回值：{}

解决思路

寻找链表的倒数第 k 个节点，核心是避免两次遍历（先算长度再找位置），最优方案是使用双指针法（快慢指针）：

1. 原理：让快指针先移动 k 步，然后快慢指针同时移动，当快指针到达链表尾部时，慢指针所在位置就是倒数第 k 个节点。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public class FindKthToTail {
    /**
     * 寻找链表的倒数第k个节点
     * @param head 链表头节点
     * @param k 倒数第k个位置（k>0）
     * @return 倒数第k个节点，若不存在返回null
     */
    public ListNode findKthToTail(ListNode head, int k) {
        // 边界条件：链表为空或k不合法
        if (head == null || k <= 0) {
            return null;
        }

        // 初始化快慢指针
        ListNode fast = head;
        ListNode slow = head;

        // 快指针先行k步
        for (int i = 0; i < k; i++) {
            // 若快指针提前遇到null，说明链表长度小于k
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        // 快慢指针同步移动，直到快指针到达尾部
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 此时slow即为倒数第k个节点
        return slow;
    }
}

1. 两个链表的第一个公共结点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n≤1000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

返回值描述：

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

示例1

输入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

示例2

输入：{1},{2,3},{}
返回值：{}
说明：2个链表没有公共节点 ,返回null，后台打印{}

解决思路

寻找两个无环单向链表的第一个公共节点，核心是让两个链表的指针 “对齐长度” 后同步遍历，避免暴力匹配的低效。最优方案是双指针同步法（又称 “交叉遍历法”），原理如下：

1. 核心逻辑：设链表 A 长度为lenA，链表 B 长度为lenB，公共部分长度为lenC。则链表 A 的非公共部分长度为lenA - lenC，链表 B 的非公共部分长度为lenB - lenC。

   1. 让指针pA从 A 头出发，遍历完 A 后再遍历 B；指针pB从 B 头出发，遍历完 B 后再遍历 A。
   2. 当两个指针都遍历了lenA + lenB - lenC个节点时，会同时到达第一个公共节点（若存在）；若不存在公共节点，则最终都指向null。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class FindKthToTail {
    /**
     * 寻找链表的倒数第k个节点
     * @param head 链表头节点
     * @param k 倒数第k个位置（k>0）
     * @return 倒数第k个节点，若不存在返回null
     */
    public ListNode findKthToTail(ListNode head, int k) {
        // 边界条件：链表为空或k不合法
        if (head == null || k <= 0) {
            return null;
        }

        // 初始化快慢指针
        ListNode fast = head;
        ListNode slow = head;

        // 快指针先行k步
        for (int i = 0; i < k; i++) {
            // 若快指针提前遇到null，说明链表长度小于k
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }

        // 快慢指针同步移动，直到快指针到达尾部
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 此时slow即为倒数第k个节点
        return slow;
    }
}

1. 判断一个链表是否为回文结构

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0≤n≤105，链表中每个节点的值满足 ∣val∣≤107

示例1

输入：{1}
返回值：true

示例2

输入：{2,1}
返回值：false
说明：2->1

示例3

输入：{1,2,2,1}
返回值：true
说明：1->2->2->1

解决思路

判断链表是否为回文结构，核心是验证链表正序和逆序是否一致。由于链表无法像数组那样随机访问，需结合快慢指针找中点和反转后半段链表的方法，实现时间复杂度 O (n)、空间复杂度 O (1) 的高效解法：

1. 找链表中点：用快慢指针，快指针走 2 步，慢指针走 1 步，当快指针到达尾部时，慢指针指向中点（偶数长度时指向左中点）。
2. 反转后半段链表：从慢指针的下一个节点开始反转，得到后半段的逆序链表。
3. 对比前后两段：从头节点和反转后的后半段头节点开始，依次比较值是否相等，全部相等则为回文。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class IsPalindrome {
    /**
     * 判断链表是否为回文结构
     * @param head 链表头节点
     * @return 是回文返回true，否则返回false
     */
    public boolean isPalindrome(ListNode head) {
        // 边界条件：空链表或单节点链表都是回文
        if (head == null || head.next == null) {
            return true;
        }

        // 步骤1：找链表中点（慢指针最终指向中点）
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;       // 慢指针走1步
            fast = fast.next.next;  // 快指针走2步
        }

        // 步骤2：反转后半段链表（从slow.next开始）
        ListNode reversedHead = reverseList(slow.next);

        // 步骤3：对比前半段和反转后的后半段
        ListNode p1 = head;         // 前半段指针
        ListNode p2 = reversedHead; // 反转后半段指针
        boolean result = true;

        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // （可选）恢复链表结构（如果需要保持原链表）
        slow.next = reverseList(reversedHead);

        return result;
    }

    /**
     * 反转链表（辅助函数）
     */
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

1. 删除有序链表中重复的元素（1）

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次 *例如： **给出的链表为1→1→2,返回1→2. *给出的链表为1→1→2→3→3,返回1→2→3.

数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足 ∣val∣≤100

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1

输入：{1,1,2}
返回值：{1,2}

示例2

输入：{}
返回值：{}

解决思路

删除有序链表中的重复元素，核心是利用链表的有序性（相同元素连续出现），通过一次遍历完成去重。具体思路：

1. 使用一个指针curr从链表头部开始遍历。

2. 比较当前节点curr与下一个节点curr.next的值：

   1. 若值相同，说明重复，将curr.next指向curr.next.next（跳过重复节点）。
   2. 若值不同，curr指针后移，继续检查下一组节点。

3. 遍历结束后，链表中所有元素均只出现一次。

/**
 * 定义链表节点
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class DeleteDuplicates {
    /**
     * 删除有序链表中的重复元素，使每个元素只出现一次
     * @param head 链表头节点
     * @return 去重后的链表头节点
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 边界条件：空链表或单节点链表无需去重
        if (head == null || head.next == null) {
            return head;
        }

        ListNode curr = head; // 遍历指针

        // 遍历链表，直到最后一个节点
        while (curr.next != null) {
            if (curr.val == curr.next.val) {
                // 跳过重复节点
                curr.next = curr.next.next;
            } else {
                // 不重复则移动指针
                curr = curr.next;
            }
        }

        return head;
    }
}