一、链表中环的入口结点给一个长度为n链表若其中包含环请找出该链表的环的入口结点否则返回null。数据范围 n≤100001结点值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≤1050≤≤1090≤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, n2.删除了链表的倒数第 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 的起点是 headp2 的起点是 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; } }运行结果 链表（3）
一、链表中环的入口结点给一个长度为n链表若其中包含环请找出该链表的环的入口结点否则返回null。数据范围 n≤100001结点值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≤1050≤≤1090≤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, n2.删除了链表的倒数第 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 的起点是 headp2 的起点是 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; } }运行结果