25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode hair = new ListNode(0);
hair.next = head;
ListNode pre = hair;
while (head != null) {
ListNode tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail.next;
if (tail == null) {
return hair.next;
}
}
ListNode nex = tail.next;
ListNode[] reverse = myReverse(head, tail);
head = reverse[0];
tail = reverse[1];
// 把子链表重新接回原链表
pre.next = head;
tail.next = nex;
pre = tail;
head = tail.next;
}
return hair.next;
}
public ListNode[] myReverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode p = head;
while (prev != tail) {
ListNode nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return new ListNode[]{tail, head};
}
}reverseKGroup方法接受两个参数：head是链表的头节点，k是每组的节点数。- 创建一个哑节点
hair，它的next指向head，这样可以方便地处理头节点的翻转，并最终返回翻转后的链表。 - 使用
pre指针来记录当前要翻转的组的前一个节点。 - 在
while循环中，首先检查剩余的节点数是否至少有k个。这是通过一个for循环实现的，如果不足k个，直接返回hair.next。 - 如果剩余节点数足够，则找到当前组的尾节点
tail，并保存下一组的头节点nex。 - 调用
myReverse方法来翻转当前组的节点。myReverse方法返回一个包含两个元素的数组，第一个元素是翻转后的头节点，第二个元素是翻转后的尾节点。 - 将翻转后的子链表重新接回原链表，并更新
pre和head指针，以便处理下一组节点。 myReverse方法中，使用头插法来翻转链表。prev指针始终指向tail的下一个节点，而p指针遍历当前组的节点，将它们逐个插入到prev和tail之间。- 最终返回
hair.next，即翻转后的链表的头节点。
这个算法的时间复杂度是 O(n)，其中 n 是链表中的节点数，因为每个节点最多被访问两次。空间复杂度是 O(1)，因为只使用了常数个额外空间。
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
输入：head = [1], n = 1
输出：[]示例 3：
输入：head = [1,2], n = 1
输出：[1]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int l = 0;
ListNode pre = new ListNode(0);
pre.next = head;
ListNode res = pre;
while (pre.next != null) {
pre = pre.next;
l++;
}
ListNode cur = res;
if (n == l) {
return res.next.next;
}
if (n == 1) {
for (int i = 0; i < l - 1; i++) {
cur = cur.next;
}
cur.next = null;
return res.next;
}
for (int i = 0; i < l - n; i++) {
cur = cur.next;
}
ListNode temp = cur.next;
cur.next = temp.next;
return res.next;
}
}removeNthFromEnd方法接受两个参数：head是链表的头节点，n是要删除的倒数第 n 个节点。- 创建一个哑节点
pre，它的next指向head。这样可以简化边界情况的处理，比如删除的是头节点。 - 使用一个指针
res来保存哑节点的引用，以便最后返回结果。 - 通过一个
while循环来计算链表的长度l。 - 接下来，根据
n的值来决定如何删除节点：
- 如果
n等于链表的长度l，那么要删除的是头节点。直接返回res.next.next，即跳过头节点后的下一个节点。 - 如果
n等于 1，那么要删除的是尾节点。通过一个for循环找到倒数第二个节点，然后将其next指针设置为null，并返回res.next。 - 对于其他情况，通过一个
for循环找到要删除节点的前一个节点，然后将其next指针指向要删除节点的下一个节点。
- 最后返回
res.next，即删除指定节点后的链表头节点。
代码中有几个地方可以优化：
- 在计算链表长度
l的同时，就可以直接找到要删除节点的前一个节点，而不需要两个独立的循环。 - 当
n等于 1 时，可以直接在计算长度的循环中处理，而不需要单独的循环。
以下是优化后的代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
// Second is now the node before the node to be deleted
second.next = second.next.next;
return dummy.next;
}
}
在这个优化后的代码中，我们使用两个指针 first 和 second，它们之间保持 n 个节点的距离。当 first 指针到达链表的末尾时，second 指针将指向要删除节点的前一个节点。然后我们直接修改 second.next 来删除目标节点。这种方法只需要一次遍历链表，时间复杂度为 O(n)，空间复杂度为 O(1)。
