19 .删除链表倒数第n个节点
思路1：
我首先想到的就是使用两个loop来进行解决：
- 遍历所有节点，得到需要删除节点的位置。
- 再遍历一边所有节点，找到需要删除节点进行删除。
解决方案1：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 判空，检查是否为空链表
if (head == null) return null;
ListNode node = head;
// 获取整个链表长度，便于后续找到需删除节点位置
int length = 0;
while(node != null){
length++;
node = node.next;
}
// node指针已经到达最后节点，需要重置指针
node = head;
// 需删除节点的位置
int mark = length - n;
// 如果为0 表示要删除的为头节点，则返回空
if (mark == 0) return node.next;
// 创建计数器
int count = 0;
while(node != null){
count++;
if(count == mark){
// 删除
node.next = node.next.next;
break;
}
node = node.next;
}
return head;
}
}思路2：
使用双指针方法，让fast指针先行n节点，然后再让fast与slow指针一起走，最后当fast走到null，slow走到的节点就是需要删除的节点。
- 定义fast指针和指向哑节点的slow指针(哑节点（dummy node）或者哨兵节点（sentinel node）在编程中常常被用来简化边界条件的处理。这是一个特殊的节点，通常在链表的开始位置添加，其值通常无关紧要，它的主要目的是使我们在处理头节点时更加方便。)
- 先使用第一个循环让fast先走n
- 使用第二个循环，两个指针一同走，直到 fast == null
- 删除slow
解决方案2
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = head;
ListNode slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
118, 杨辉三角
思路:
使用迭代方法解决，我们可以将所有的数向左移动，变成如下结构：
1
11
121
1331
14641观察可知，每行第一个和最后一个不变都为1，中间的每个数为上一行正上方和左上方数相加，
所以我们需要：
- 创建一个数组用于存储整个表 ArrayList<List<Integer>>
- 创建一个数组用于存储当前行 ArrayList<Integer>
解决方案
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> row = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
row.add(0, 1);
for (int j = 1; j < row.size() - 1; j++)
row.set(j, row.get(j) + row.get(j + 1));
res.add(new ArrayList<>(row));
}
return res;
}
}
