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

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;  // 没有环}
}

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