专业网站名词解释,王野动力,免费字体,wordpress关于本站19 .删除链表倒数第n个节点 思路1#xff1a;
我首先想到的就是使用两个loop来进行解决#xff1a;
遍历所有节点#xff0c;得到需要删除节点的位置。再遍历一边所有节点#xff0c;找到需要删除节点进行删除。
解决方案1#xff1a;
class Solution {public ListNod…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走到nullslow走到的节点就是需要删除的节点。
定义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中间的每个数为上一行正上方和左上方数相加
所以我们需要
创建一个数组用于存储整个表 ArrayListListInteger创建一个数组用于存储当前行 ArrayListInteger
解决方案
class Solution {public ListListInteger generate(int numRows) {ListListInteger res new ArrayList();ArrayListInteger 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;}
}
