刷题打卡，第七天
题目一、876. 链表的中间结点
题目二、142. 环形链表 II
题目三、121. 买卖股票的最佳时机
题目一、876. 链表的中间结点
原题链接：876. 链表的中间结点
题目描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
解题思路：
已经给定非空链表的头节点，那么就不需要判断链表是否为空了；
我们通过循环记录链表节点的个数，将记录的个数除以2得到指针需要移动的次数，返回移动完后的节点即可。
解题代码：
/** * 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 middleNode(ListNode head) { ListNode curr = head;//创建新节点记录给定头节点 int total = 0; //total记录节点总数 while(curr != null){ //不为空 total++; //记录节点数+1 curr = curr.next;//指针指向下一节点 } for(int i = 0;i < total>>1;++i){//total>>1,相当于总数 / 2 head = head.next; //指针扫过一半节点，抵达中间节点 } return head;//返回中间节点 } }
提交结果：
题目二、142. 环形链表 II
原题链接：142. 环形链表 II
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
解题思路：
使用不可重复的set集合来存放节点元素，不断扫描数组，若遇到无法存放节点的情况，说明节点重复，重复节点就是入环的第一个节点。
如果存在节点的下一节点为null，说明无环，直接返回null。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode pos = head; Set set = new HashSet();//创建不可重复的单列集合 while(pos != null){ //节点不为空时 if(set.add(pos)){ //节点元素放入集合中 pos = pos.next; //指针后移 }else{ //节点无法放入集合，说明已经扫描过 return pos; //直接返回，这就是入环节点 } } return null; //存在节点下一位为空，说明无环，返回空 } }
提交结果：
题目三、121. 买卖股票的最佳时机
原题链接：121. 买卖股票的最佳时机
题目描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解题思路：
遍历数组中每一天的股价，记录最低值min，遍历到比min大的股价，就计算差值，最终返回最大的差值，就代表最大利润。
解题代码：
class Solution { public int maxProfit(int[] prices) { int min = prices[0];//表示最低的价格 int max = 0; //表示最高的利润 for(int i = 0;i < prices.length;++i){ if(prices[i] <= min){//如果这天股价更低 min = prices[i]; //将股价记录为min }else if(max < prices[i]-min){//如果这天股价高，计算与min差值 max = prices[i]-min; //若结果高于记录max，更新最大利润 } } return max; //返回最大利润 } }
贵在坚持：
