一、斐波那契数列
https://leetcode-cn.com/problems/fibonacci-number/.题目描述：
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例代码
// O(n)
public static int fib2(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i++) {
int sum = first + second;
first = second;
second = sum;
}
return second;
}
二、237. 删除链表中的节点 https://leetcode-cn.com/problems/delete-node-in-a-linked-list/.
题目描述：
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。现有一个链表 -- head = [4,5,1,9]，它可以表示为:
001.png示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
思路分析：
从链表里删除一个节点 node 的最常见方法是修改之前节点的 next 指针，使其指向之后的节点。所以，我们可将要删除的节点的值替换为它后面节点中的值，然后删除它之后的节点。 如下图所示：
001.png002.png
示例代码
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
三、206. 反转链表
https://leetcode-cn.com/problems/reverse-linked-list/.题目描述：
反转一个单链表。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
思路分析1：
① 递归思路
假设head节点是5 那么下一个节点是4,下一个是3，2，1，null
如果此时我传入head.next,即传入4，返回的newHead为 1，2，3，4，null.
如果传入3，返回的newHead为1，2，3，null
......003-1 .png003-2.png
示例代码
① 递归方式
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
思路分析2：
② 迭代思路
迭代的思路类似于交换两个数据，所以需要引入一个临时变量tmp,思路如下：
①.先让tmp指向head的next
②.再让head的next指向newHead
③.再让newHead指向head
④.让head指向临时的tmp,即tmp指向的head.next
第二次循环：
①.先让tmp指向head的next
②.再让head的next指向newHead
③.让newHead指向head
④.让head指向临时的tmp,即tmp指向的head.next
以此类推,如下图所示：003-3.jpg
示例代码
① 迭代方式
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
四、141. 环形链表 https://leetcode-cn.com/problems/linked-list-cycle/.
题目描述：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
004.png
思路分析：
题目描述：
由题可知，示例1和示例2有环，示例3无环。这题目经典解决思路是“快慢指针”思想，首先设置一个慢指针slow 指向3，快指针 fast，指向2，快指针fast每次走两步，慢指针slow每次走一步，如果是有环的话，走到一定时刻，都会进入环，如果是有环，某一时刻一定会相遇。相遇即有环。
如果没有环的话，快指针fast先达到空，即null，那么意味着没有环。
思路如下图所示：
004-2.jpg
示例代码
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
五、20. 有效的括号
https://leetcode-cn.com/problems/valid-parentheses/solution/.
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
005.png
思路分析：
005-2.jpg
示例代码
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int len = s.length();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') { // 左括号
stack.push(c);
} else { // 右括号
if (stack.isEmpty()) return false;
char left = stack.pop();
if (left == '(' && c != ')') return false;
if (left == '{' && c != '}') return false;
if (left == '[' && c != ']') return false;
}
}
return stack.isEmpty();
}
记录一下学习链表和栈的历程，后序持续更新中~
