《五月集训》（第12天）——链表

前言：

五月集训，前面为学习内容，想要一起学习的可以看一看，最后的才是五月集训每天的作业。

一、知识点

一般地，单向链表每个节点包含：
一个变量存储自身的值，一个连接点链接下一个节点。

二、课堂习题

这里的题均出自《算法零基础100讲》
暑假前不会做咯。

三、作业

1290. 二进制链表转整数
237. 删除链表中的节点
剑指 Offer II 024. 反转链表
1019. 链表中的下一个更大节点
解题思路：
1.将每个节点中的值取出×2累加即可；
2.将要删除的节点值变成下一个节点的值，然后链接下一个节点连接的节点（相当于把自己变成下一个节点，然后出去下一个节点）；
3.定义两个指针，一个ans空指针，一个cur指向头指针，cur不断后移，将让每次cur指向的节点链接到ans上，实现反转；
4.从尾部开始遍历数组，不断放入到栈中，将较小的弹出，使栈中只剩下比数组元素大的值，然后对结果数组赋值。
代码：

/** * 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 int getDecimalValue(ListNode head) { int sum = 0; while(head != null){     sum = sum * 2 + head.val;     head = head.next; } return sum;    }}

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next;    }}

/** * 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 reverseList(ListNode head) { if(head == null){     return head; } ListNode ansList = null; ListNode cur = head; while(cur != null){     ListNode temp = cur.next;     cur.next = ansList;     ansList = cur;     cur = temp; } return ansList;    }}

/** * 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 int[] nextLargerNodes(ListNode head) { if (head == null) {     return null; } ArrayList<Integer> list = new ArrayList<>(); int n = 0; while (head != null) {     list.add(head.val);     n++;     head = head.next; } Stack<Integer> stack = new Stack<>(); int[] ans = new int[n];  for (int i = n - 1; i >= 0; i--) {     while (!stack.empty() && stack.peek() <= list.get(i)) {  stack.pop();     }     ans[i] = stack.empty() ? 0 : stack.peek();     stack.push(list.get(i)); } return ans;    }}

四、总结

对于算法的掌握还是不够熟练，需要进行反复训练！
另外，剩下的课堂训练题目留到下个月的集训啦(●ˇ∀ˇ●)

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖