LeetCode刷题(链表&栈)

一、斐波那契数列
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.png 002.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 .png 003-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();
    }

记录一下学习链表和栈的历程，后序持续更新中~