算法练习——删除链表的倒数第 N 个结点

2021年1月19日LeetCode每日一题为1584. 连接所有点的最小费用,这道题想到了将其所有点的距离算出来构建出一个矩阵然后用kruskal算法就能将答案算出来,但是对kruskal算法不够熟悉,基本上忘记是怎么样的一个思路了,因此完成了19. 删除链表的倒数第 N 个结点,在做这这题时,注意是倒数第N个节点,那么我们就可以将链表先遍历一遍计算出长度,然后将指针指向需要移除的节点的前一个节点,将前一个节点的next指针指向移除的节点的下一个节点。如果是一个节点的情况,没有为其构建一个指向头部的指针的话就没办法移除了,因此在此之前需要构建一个指针头,然后将倒数第n个节点删除后,返回这个指针头后面的节点,就是符合题设的答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 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 cur = head;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
cur = new ListNode(0, head);
ListNode ret = cur;
for (int i = 0; i < size - n; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
return ret.next;
}
}

今天发现自己树的构建都不太会写了,果然之前学习的并不扎实,需要勤以练习,简单又熟悉的都是线性结构。距离过年还有三个星期,在这三个星期里,应该能够将基本的数据结构和算法都搞定,加油!