Java 八道经典面试题之链表题

什么是链表？

链表是一种常见的线性数据结构，与数组最大的区别是：链表的元素在物理空间上不是连续的，而是靠指针相连。链表由一连串的结点组成，每个结点都包含两部分内容，一部分是存储数据的数据域，另一部分是存储下一个结点地址的指针域，也可以包含前一个结点的地址指针域（双向链表）。

单链表 & 双向链表

单链表是每个结点只指向它的后继结点，没有指向前一个结点的指针。常见的有单向链表、循环单向链表、静态链表。双向链表是每个结点既有指向后继结点的指针，也有指向前驱结点的指针，和单向链表相比，双向链表可以从任意一个结点开始往前或往后遍历。

链表的操作

链表的基本操作包括：插入、删除、遍历。

链表的插入操作通常有三种：在链表头部插入结点、在链表尾部插入结点、在链表中间插入结点。

链表的删除操作通常有两种：删除链表中指定结点、按照位置删除链表的结点。

遍历链表的方法主要有两种：通过循环遍历链表，递归方式遍历链表。

经典面试题：反转链表

题目描述

输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

分析步骤

1. 定义三个指针：当前结点指针，前驱结点指针，后继结点指针；
2. 遍历链表，不断更新指针，变换指针方向，实现链表反转；
3. 时间复杂度 O(n)，空间复杂度 O(1)。

代码示例

public ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;  //保存下一个结点
        cur.next = pre;  //反转指针
        pre = cur;  //更新前驱结点指针
        cur = next;  //更新当前结点指针
    }
    return pre;  //返回反转后的头结点指针
}

示例说明

以链表 1->2->3->4->5 为例，反转后的链表应该为 5->4->3->2->1。

我们设置三个指针：pre、cur、next，分别指向前驱结点、当前结点和后继结点。在遍历链表的过程中，不断修改这三个指针的指向，即可实现链表的反转。最后返回 pre 即可。

如下所示，指针的变化顺序为：1->2->3->4->5，变为 5->4->3->2->1。

初始化：
pre = null；
cur = 1 -> 2 -> 3 -> 4 -> 5；
next = null；

第一次遍历：
next = cur.next = 2 -> 3 -> 4 -> 5；
cur.next = pre = null；
pre = cur = 1 -> null；
cur = next = 2 -> 3 -> 4 -> 5；

第二次遍历：
next = cur.next = 3 -> 4 -> 5；
cur.next = pre = 1 -> null；
pre = cur = 2 -> 1 -> null；
cur = next = 3 -> 4 -> 5；

第三次遍历：
next = cur.next = 4 -> 5；
cur.next = pre = 2 -> 1 -> null；
pre = cur = 3 -> 2 -> 1 -> null；
cur = next = 4 -> 5；

第四次遍历：
next = cur.next = 5 -> null；
cur.next = pre = 3 -> 2 -> 1 -> null；
pre = cur = 4 -> 3 -> 2 -> 1 -> null；
cur = next = null；

返回结果：pre = 5 -> 4 -> 3 -> 2 -> 1 -> null；

经典面试题：链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。

分析步骤

1. 双指针法：定义两个指针 p1、p2，让 p1 先走 k-1 步，然后再同时移动 p1 和 p2，当 p1 到达链表尾时，p2 指向的即是链表中倒数第 k 个结点；
2. 先遍历链表获取链表长度 n，然后从头开始遍历到第 n-k+1 个结点即可；
3. 时间复杂度 O(n)，空间复杂度 O(1)。

代码示例

public ListNode findKthToTail(ListNode head, int k) {
    ListNode p1 = head;
    ListNode p2 = head;
    for (int i = 0; i < k; i++) {
        if (p1 == null) return null;  //特判 k 大于链表长度的情况
        p1 = p1.next;
    }
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

示例说明

以链表 1->2->3->4->5 为例，要求找到倒数第 2 个结点，即输出 4。

我们设置两个指针：p1、p2，初始时均指向链表头结点。p1 先走 1 步，p2 保持不动；p1 再走 1 步，p2 也走一步，此时 p1 到达了第 3 个结点，p2 到达了第 2 个结点；以此类推，当 p1 走到链表结尾时，p2 指向的结点即为所求。

public ListNode findKthToTail(ListNode head, int k) {
    ListNode p1 = head;
    ListNode p2 = head;
    for (int i = 0; i < k-1; i++) {  //p1 先走 k-1 步
        if (p1 == null) return null;  //特判 k 大于链表长度的情况
        p1 = p1.next;
    }
    while (p1.next != null) {  //同时移动 p1 和 p2
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

总结

针对链表题，首先要了解链表的基本操作，包括插入、删除、遍历；其次，掌握链表的特点与算法思想，常见的题目包括反转链表、链表中倒数第k个结点、删除链表中重复的结点等等。在实际应用中，还需要注意链表元素为空、链表只有一个元素、链表长度小于 k 等边界情况的处理，避免空指针错误等问题。