一、链表中环的入口结点
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围： n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { // 快、慢指针 // 假设有环，二者终会相遇 // 在相遇点，让其中一个回到起点，随后二者以相同的步伐走（每次走一步，最终二者将在环的入口节点相遇） ListNode fast, slow; fast = slow = pHead; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { fast = pHead; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } } return null; } }运行结果
二、链表中倒数最后k个结点
输入一个长度为 n 的链表，设链表中的元素的值为，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤n≤105，0≤≤109，0≤k≤109
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { // 换个角度，倒数第 k 个节点可以转换成该节点到末尾 null 的距离（即往后走几步到达 null，这个几就是 k） // 所以不妨设置两个指针 p1、p2。先让 p1 往前走 k 步，这是为了让 p1 和 p2 保持恒定的间距 k。 // 随后 p1、p2 同步走，一次走一步。 // 当 p1 先走到 null 时，p2 所指向的节点即为倒数第 k 个节点 ListNode p1, p2; p1 = p2 = pHead; // p1 先走 k 步 for (int i = 0; i < k; i++) { if (p1 == null && i < k) { // 链表长度小于 k 时，p1 会在未走满 k 步前提前走到 null return null; } p1 = p1.next; } // p1、p2 同步走 while (p1 != null) { p1 = p1.next; p2 = p2.next; } return p2; } }运行结果
三、删除链表的倒数第n个节点
给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
例如，给出的链表为: 1→2→3→4→5, n=2.
删除了链表的倒数第 nn个节点之后,链表变为1→2→3→5.
数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(n)
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; // 还是同样的 p1, p2 // 只不过 p2 要寻找的目标是倒数第 n 个节点的前驱节点 // 现在 p1 的起点是 head，p2 的起点是 dummy // 题目保证 n 是有效的 ListNode p1 = head, p2 = dummy; // p1 先走 n 步 for (int i = 0; i < n; i++) { p1 = p1.next; } // p1、p2 一起走 while (p1 != null) { p1 = p1.next; p2 = p2.next; } // 此时 p2 是倒数第 n 个节点的前驱节点 p2.next = p2.next.next; return dummy.next; } }运行结果
