前言
之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两天晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀
链表的合集
字符串
- 六六力扣刷题字符串之反转字符串
- 六六力扣刷题字符串之反转字符串2
- 六六力扣刷题字符串之替换空格
- 六六力扣刷题字符串之反转字符串中的单词
- 六六力扣刷题字符串之找出字符串中第一个匹配项的下
- 六六力扣刷题字符串之重复的子字符串
双指针
题目
给你一个链表,删除链表的倒数第 n
**个结点,并且返回链表的头结点。
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2:
输入:head = [1], n = 1 输出:[] 示例 3:
输入:head = [1,2], n = 1 输出:[1]双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的,但要注意一些细节。
题解
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的,但要注意一些细节。
双指针
由于我们需要找到倒数第 nn 个节点,因此我们可以使用两个指针 first 和 second 同时对链表进行遍历,并且 first 比 second 超前 nn 个节点。当 first 遍历到链表的末尾时,second 就恰好处于倒数第 nn 个节点。
具体地,初始时 first 和 second 均指向头节点。我们首先使用first 对链表进行遍历,遍历的次数为 nn。此时,first 和 second 之间间隔了 n-1n−1 个节点,即 first 比second 超前了 nn 个节点。
在这之后,我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 nn 个节点。
根据方法一和方法二,如果我们能够得到的是倒数第 nn 个节点的前驱节点而不是倒数第 nn 个节点的话,删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点,其余的操作步骤不变。这样一来,当 first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; ++i) { first = first.next; } while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; ListNode ans = dummy.next; return ans; } }
计算链表长度
/** * 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(0, head); int length = getLength(head); ListNode cur = dummy; for (int i = 1; i < length - n + 1; ++i) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = dummy.next; return ans; } public int getLength(ListNode head) { int length = 0; while (head != null) { ++length; head = head.next; } return length; } }
这个也可以,只要知道长度,我们就知道在那个地方做 next
结束
好了,今天这题2个方法都告诉大家了,大家可以学习下,加油,我们明天继续,相信时间的力量!