做淘宝优惠网站,泰州网站建设价格,邢台163,c语言精品课程网站开发1. 力扣19#xff1a;删除链表的倒数第N个节点
1.1 题目#xff1a;
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a; …1. 力扣19删除链表的倒数第N个节点
1.1 题目
给你一个链表删除链表的倒数第 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]提示
链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz
进阶你能尝试使用一趟扫描实现吗
1.2 思考
简单的一个数学问题假设这条链表的长度是k我们要删除的是链表的倒数第n个节点。
要删除倒数第n个节点其实就是要找到倒数第n1个节点。
last节点走几步才能到倒数第n1个节点呢k - (n 1)步。
front节点提前走k - (k - (n 1))步然后frontlast一起走直到frontnull为止此时last刚好停在倒数第n1个节点上。
不懂的画个图就很好的理解了。
1.3 题解
/*** 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) {// 因为头节点也又可能被删除所以有必要添加一个哨兵节点ListNode dummy new ListNode(10086, head);// 前后指针都从哨兵节点开始遍历ListNode front dummy;ListNode last dummy;// 为什么i要是n1呢int i n 1;while(i-- 0){front front.next;}while(front ! null){front front.next;last last.next;}// last指针的下一个节点就是要删除的节点last.next last.next.next;return dummy.next;}
}
2. 力扣61旋转链表
2.1 题目
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
示例 1 输入head [1,2,3,4,5], k 2 输出[4,5,1,2,3]
示例 2 输入head [0,1,2], k 4
输出[2,0,1]提示
链表中节点的数目在范围 [0, 500] 内-100 Node.val 1000 k 2 * 109
2.2 思考
注释写的比较清楚了。
2.3 题解
/*** 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 rotateRight(ListNode head, int k) {// 如果空链表直接返回if(head null){return null;}// k可能会非常大可以把k变小一点ListNode p head;int n 0;while(p ! null){n;p p.next;}// n不会为0因为空链表的情况已经提前返回k k % n;// k为0相当于节点都不需要移动if(k 0){return head;}// 头节点可能会发生修改所以哨兵节点还是必要的ListNode dummy new ListNode(10086, head);// 由题每个节点向右移动k个位置// 找到倒数第k1个位置不断把倒数第k1个位置的后面的节点// 移到链表的头部。ListNode front dummy;ListNode last dummy;int i k1;while(i-- 0){front front.next;}while(front ! null){front front.next;last last.next;}// 此时last节点指向的就是倒数第k1个节点// 从哨兵节点后开始开始尾插法ListNode dummy_copy dummy;while(last.next ! null){ListNode delete last.next;last.next last.next.next;delete.next dummy_copy.next;dummy_copy.next delete;dummy_copy delete;}return dummy.next;}
}
3. 力扣1721交换链表中的节点
3.1 题目
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后返回链表的头节点链表 从 1 开始索引。
示例 1 输入head [1,2,3,4,5], k 2
输出[1,4,3,2,5]示例 2
输入head [7,9,6,6,7,8,3,0,9,5], k 5
输出[7,9,6,6,8,7,3,0,9,5]示例 3
输入head [1], k 1
输出[1]示例 4
输入head [1,2], k 1
输出[2,1]示例 5
输入head [1,2,3], k 2
输出[1,2,3]提示
链表中节点的数目是 n1 k n 1050 Node.val 100
3.2 思考
看注释。
3.3 题解
/*** 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 swapNodes(ListNode head, int k) {// 空链表直接返回if(head null){return null;}// 因为头节点可能会改变所以哨兵节点有必要ListNode dummy new ListNode(10086, head);ListNode front dummy;ListNode last dummy;// 假如链表的总长度为n// front走了k步到达了链表正第k个节点记录下来// 此时front和last一起走一起走了(n - k)步// frontnull时last到达了链表倒数第k个节点// n - (n - k)从后i面数刚好是倒数第k个while(k-- 0){front front.next;}// 此时将front指向的节点记录下来ListNode p1 front;while(front ! null){front front.next;last last.next;}//此时将last指向的节点记录下来ListNode p2 last;// 交换int temp;temp p1.val;p1.val p2.val;p2.val temp;return dummy.next;}
}
