当前位置：首页 > news >正文

【数据结构与算法 | 灵神题单 | 前后指针(链表)篇】力扣19， 61，1721

news 来源：原创 2024/9/20 4:46:04

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]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

1.2 思考

简单的一个数学问题，假设这条链表的长度是k，我们要删除的是链表的倒数第n个节点。

要删除倒数第n个节点，其实就是要找到倒数第n+1个节点。

last节点走几步才能到倒数第n+1个节点呢？k - (n + 1)步。

front节点提前走k - (k - (n + 1))步，然后front，last一起走，直到front==null为止，此时last刚好停在倒数第n+1个节点上。

不懂的画个图就很好的理解了。

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要是n+1呢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 <= 100
0 <= 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个位置// 找到倒数第k+1个位置，不断把倒数第k+1个位置的后面的节点// 移到链表的头部。ListNode front = dummy;ListNode last = dummy;int i = k+1;while(i-- > 0){front = front.next;}while(front != null){front = front.next;last = last.next;}// 此时last节点指向的就是倒数第k+1个节点// 从哨兵节点后开始，开始尾插法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]

提示：

链表中节点的数目是 n
1 <= k <= n <= 105
0 <= 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)步// front==null时，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;}
}