基于链表的基础笔试/面试题

1. 反转链表

问题描述：反转一个单向链表。

示例：

输入：1 → 2 → 3 → 4 → 5

输出：5 → 4 → 3 → 2 → 1

class ListNode {int val;ListNode next;ListNode(int x) {val = x;}
}public class LinkedList {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTemp = curr.next; // 保存下一个节点curr.next = prev;              // 当前节点反转指向前一个节点prev = curr;                   // prev移动到当前节点curr = nextTemp;               // curr移动到下一个节点}return prev; // prev为新的头节点}
}

2. 查找链表中间节点

问题描述：给定一个单链表，找出链表的中间节点。如果链表有两个中间节点，则返回第二个中间节点。

示例：

输入：[1, 2, 3, 4, 5]

输出：3

输入：[1, 2, 3, 4, 5, 6]

输出：4

public class LinkedList {public ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;        // 慢指针每次走一步fast = fast.next.next;   // 快指针每次走两步}return slow;  // 当快指针到达尾部时，慢指针正好在中间}
}

3. 环形链表检测

问题描述：给定一个链表，判断链表是否有环。

示例：

输入：[3, 2, 0, -4]，环形链表，从节点2开始有环

输出：true

public class LinkedList {public boolean hasCycle(ListNode head) {if (head == null) return false;ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;        // 慢指针每次走一步fast = fast.next.next;   // 快指针每次走两步if (slow == fast) {      // 快慢指针相遇，表示有环return true;}}return false;  // 没有环}
}

4. 删除链表倒数第N个节点

问题描述：删除链表的倒数第N个节点，并返回链表的头节点。

示例：

输入：[1, 2, 3, 4, 5], N = 2

输出：[1, 2, 3, 5]

public class LinkedList {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode fast = head;ListNode slow = head;// 快指针先走n步for (int i = 0; i < n; i++) {fast = fast.next;}// 如果fast为null，说明要删除的是头节点if (fast == null) {return head.next;}// 快慢指针同时走while (fast != null && fast.next != null) {fast = fast.next;slow = slow.next;}// 删除慢指针的下一个节点slow.next = slow.next.next;return head;}
}

5. 合并两个有序链表

问题描述：将两个升序链表合并为一个新的升序链表，返回合并后的链表。

示例：

输入：1 → 2 → 4, 1 → 3 → 4

输出：1 → 1 → 2 → 3 → 4 → 4

public class LinkedList {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);  // 创建一个虚拟头节点ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}// 将剩余的部分连接上if (l1 != null) {current.next = l1;}if (l2 != null) {current.next = l2;}return dummy.next;  // 返回合并后的链表头}
}

6. 删除链表中的重复元素

问题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例：

输入：1 → 1 → 2 → 3 → 3

输出：1 → 2 → 3

public class LinkedList {public ListNode deleteDuplicates(ListNode head) {ListNode current = head;while (current != null && current.next != null) {if (current.val == current.next.val) {current.next = current.next.next;  // 跳过重复节点} else {current = current.next;  // 继续遍历}}return head;}
}

7. 找到链表的环入口节点

问题描述：给定一个链表，如果链表中有环，找出环的入口节点。如果没有环，返回null。

示例：

输入：3 → 2 → 0 → -4，环形链表，环的入口是节点2

输出：2

public class LinkedList {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;// 快慢指针检测是否有环while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {  // 如果快慢指针相遇，说明有环ListNode entry = head;while (entry != slow) {  // 找环的入口entry = entry.next;slow = slow.next;}return entry;  // 返回环的入口节点}}return null;  // 没有环}
}

---

上述是一些面试中常见问题，还有一部分比较少见但是也会遇上的问题：

1. 链表的交集：如何找到两个链表的交集？

2. 链表的差集：如何找到两个链表的差集？

3. 链表的环形数组：如何判断一个链表是否可以构成环形数组？

4. 复制带有随机指针的链表：如何复制一个包含随机指针的链表？

5. 奇偶排序链表：如何对链表进行奇偶排序？

6. 链表的插入排序：如何使用插入排序算法对链表进行排序？

7. 链表的递归遍历：如何使用递归方法遍历链表？

8. 链表的扁平化：如何将一个嵌套的链表扁平化？

9. 链表的旋转：如何将链表向右旋转k个位置？

10. 链表的重新排列：如何将链表中的节点重新排列，使得奇数索引的节点和偶数索引的节点交替出现？

11. 链表的分组：如何将链表中的节点分成k个大小相等的组？

12. 链表的压缩：如何压缩链表，使得所有值为val的节点合并为一个节点？

可以试着实现这些笔试题，在面试时更有自信！！！

不积跬步，无以至千里 --- xiaokai