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;}
}
