目录

第三天

第一题、合并两个有序链表

 思路

代码

第二题、反转链表

 思路一

代码一

思路二

第四天

第一题、链表的中间结点

 思路

代码

第二题、环形链表 II

 思路一

代码一

思路二

代码二

第五天

第一题、买卖股票的最佳时机

思路一

代码一

思路二

代码二

第二题、最长回文串

思路

代码

---

第三天

第一题、合并两个有序链表

 思路

首先碰到链表问题，我们第一时间需要想到链表判空问题，然后在继续写代码，然后我这里采用的是递归的解法，其实合并两个有序链表和合并俩个数组差不多，这么说不知各位看官老爷有没有豁然开朗，因为是链表不用考虑数组扩容的问题，所以我直接是从两个链表的头节点开始比较，然后看谁大谁小，小的就确定位置了，大的值和小的那个值的next的值比较，这样递归下去每个值的位置就确定好了，最后返回最开始的那个头节点。

代码

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}if (list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}

第二题、反转链表

 思路一

使用辅助栈求解，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

代码一

public ListNode ReverseList(ListNode head) {Stack<ListNode> stack= new Stack<>();//把链表节点全部摘掉放到栈中while (head != null) {stack.push(head);head = head.next;}if (stack.isEmpty())return null;ListNode node = stack.pop();ListNode dummy = node;//栈中的结点全部出栈，然后重新连成一个新的链表while (!stack.isEmpty()) {ListNode tempNode = stack.pop();node.next = tempNode;node = node.next;}//最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环node.next = null;return dummy;
}

思路二

双链表求解，也就是是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。

public ListNode ReverseList(ListNode head) {//新链表ListNode newHead = null;while (head != null) {//先保存访问的节点的下一个节点，保存起来ListNode temp = head.next;//每次访问的原链表节点都会成为新链表的头结点，head.next = newHead;//更新链表newHead = head;head = temp;}return newHead;
}

第四天

第一题、链表的中间结点

 思路

快慢指针，用两个指针 slow 与 fast 一起遍历链表，开始的时候两个指针都指向头节点，slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

代码

    public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}

第二题、环形链表 II

 思路一

还是快慢指针，看下图

 首先我们知道当两指针相遇就是存在环，然后找环入口那个推导过程我就不说了，这里直接说结论，当两指针相遇后，随便拿一个指针回到头节点，然后两个指针这个时候以相同的速度开始走，再次相遇的时候就是环的入口点。

代码一

    public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (true) {if (fast == null || fast.next == null) {return null;}fast = fast.next.next;slow = slow.next;if (fast == slow) break;}fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}

思路二

利用哈希的思想，我们遍历链表的节点，把每个节点记录下来，要是后面再次遍历到这个节点那么就说明有环，然后返回这个节点就可以了。

代码二

    public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode cur = head;while (cur != null) {if (set.contains(cur)) {return cur;}else {set.add(cur);}cur = cur.next;}return null;}

第五天

第一题、买卖股票的最佳时机

思路一

用 maxprofit 来表示获取的最大利润，用 minprice 记录是历史最低价格，假设股票是在那天买的，然后我们的利润就是price[i] - minprice，所以这个时候我们遍历一次数组就好了。

代码一

    public int maxProfit(int[] prices) {int minprice = Integer.MAX_VALUE;int maxprofit = 0;for(int i : prices){maxprofit = Math.max(maxprofit, i - minprice);minprice = Math.min(minprice, i);}return maxprofit;}

思路二

直接暴力求解，一个个去试出最大 maxprofit 。

代码二

    public int maxProfit(int[] prices) {int maxprofit = 0;for (int i = 0; i < prices.length - 1; i++) {for (int j = i + 1; j < prices.length; j++) {int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}

第二题、最长回文串

思路

题本身不难，我就说几个需要注意的地方，首先我这是用数组来求解，因为大写字母加小写字母一共52个，所以我们创建一个容量52的数组来存储字符，然后A-Z,a-z在ASCII码表中不是连着一起的，所以我们后面存数组的时候要分开来存，然后如果某个字母有偶数个，因为偶数有对称性，可以把它全部用来构造回文串；但如果是奇数个的话，并不是完全不可以用来构建，也不是只能选最长的那个，而是只要砍掉1个，剩下的变成偶数就可以全部计入了，而奇数字母里，可以保留1个不砍，把它作为回文串的中心，所以最后还要再加回一个1，但是，如果是没有奇数的情况，这个1也不能随便加，所以还要分情况讨论。我能想到的需要注意的就这些了。

代码

    public int longestPalindrome(String s) {int[] ch = new int[26 + 26];for (char ss : s.toCharArray()) {if (ss >= 'a') {ch[ss - 'a'] += 1;} else {ch[ss - 'A' + 26] += 1;}}int res = 0;int odd = 0;for (int cc : ch) {res += cc;if (cc % 2 == 1) {odd += 1;}}return odd == 0 ? res : res - odd + 1;}