数组、链表、栈和队列-习题解析-week02

数组和链表
- 203.移除链表元素（简单）">203.移除链表元素（简单）
- 876.链表的中间结点（简单）">876.链表的中间结点（简单）
- 83.删除排序链表中的重复元素（简单）">83.删除排序链表中的重复元素（简单）
- 剑指Offer 25.合并两个排序的链表（中等）">剑指Offer 25.合并两个排序的链表（中等）
- 2.两数相加（中等）">2.两数相加（中等）
- 206.反转链表（中等）">206.反转链表（中等）
  - 递归
  - 哨兵节点 + 头插法
- 234.回文链表（中等）">234.回文链表（中等）
- 328.奇偶链表（中等）">328.奇偶链表（中等）
- 25. K个一组翻转链表（困难）">25. K个一组翻转链表（困难）
- 剑指Offer 22.链表中倒数第k个节点（简单）">剑指Offer 22.链表中倒数第k个节点（简单）
  - 遍历计算总数
  - 快慢指针
- 19.删除链表的倒数第N个结点（中等）">19.删除链表的倒数第N个结点（中等）
- 160.相交链表（简单）">160.相交链表（简单）
  - 快慢指针
- 141.环形链表（简单）">141.环形链表（简单）
  - 快慢指针
栈和队列
- 剑指Offer 09.用两个栈实现队列（简单）">剑指Offer 09.用两个栈实现队列（简单）
- 225.用队列实现栈（简单）">225.用队列实现栈（简单）
- 面试题03.05.栈排序（中等）">面试题03.05.栈排序（中等）
- 155.最小栈（简单）">155.最小栈（简单）
- 面试题03.01.三合一（简单）">面试题03.01.三合一（简单）
- 20.有效的括号（简单）">20.有效的括号（简单）
- 面试题16.26.计算器（中等）">面试题16.26.计算器（中等）
- 772.基本计算器III（困难包含括号力扣会员）">772.基本计算器III（困难包含括号力扣会员）
- 1047.删除字符串中的所有相邻重复项（简单）">1047.删除字符串中的所有相邻重复项（简单）
- 剑指Offer 31.栈的压入、弹出序列（中等）">剑指Offer 31.栈的压入、弹出序列（中等）
- 739.每日温度（中等）单调栈">739.每日温度（中等）单调栈
- 42.接雨水（困难）单调栈">42.接雨水（困难）单调栈
- 84.柱状图中最大的矩形（困难）单调栈">84.柱状图中最大的矩形（困难）单调栈
- 面试题03.06.动物收容所（中等）队列">面试题03.06.动物收容所（中等）队列
- 剑指Offer 59 - II.队列的最大值（中等）单调队列">剑指Offer 59 - II.队列的最大值（中等）单调队列
- 剑指Offer 59 - I.滑动窗口的最大值（困难）单调队列">剑指Offer 59 - I.滑动窗口的最大值（困难）单调队列

数组和链表

203.移除链表元素（简单）

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 哨兵节点
        ListNode dumyNode = new ListNode(), tmp = dumyNode;
        while(head != null) {
            if(head.val != val) {
                tmp.next = head;
                tmp = tmp.next;
            }
            head = head.next;
        }
        // 断开节点引用
        tmp.next = null;
        return dumyNode.next;
    }
}

876.链表的中间结点（简单）

/**
 * 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 slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

83.删除排序链表中的重复元素（简单）

/**
 * 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 deleteDuplicates(ListNode head) {
        ListNode resNode = new ListNode(-101), tmp = resNode;
        while(head != null) {
            if(tmp.val != head.val) {
                tmp.next = head;
                tmp = tmp.next;
            }
            head = head.next;
        }
        // 注意点，考察点
        tmp.next = null;
        return resNode.next;
    }
}

剑指Offer 25.合并两个排序的链表（中等）

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 哨兵节点 + 遍历
        ListNode dumyHead = new ListNode(), tmp = dumyHead;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                tmp.next = l1;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        if(l1 != null) {
            tmp.next = l1;
        }
        if(l2 != null) {
            tmp.next = l2;
        }
        return dumyHead.next;
    }
}

2.两数相加（中等）

206.反转链表（中等）

递归

/**
 * 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 {
    ListNode res = new ListNode();
    public ListNode reverseList(ListNode head) {
        // 递归
        if(head == null) {
            return null;
        }
        reverse(head).next = null;
        return res.next;
    }
    public ListNode reverse(ListNode node) {
        if(node.next == null) {
            res.next = node;
            return node;
        }
        ListNode tmp = reverse(node.next);
        tmp.next = node;
        return node;
    }
}

哨兵节点 + 头插法

/**
 * 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) {
        // 虚拟头结点 + 头插法
        ListNode dumyNode = new ListNode();
        while(head != null) {
            ListNode next = dumyNode.next;
            ListNode tmp = head.next;
            dumyNode.next = head;
            head.next = next;
            head = tmp;
        }
        return dumyNode.next;
    }
}

234.回文链表（中等）

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newNode =  reverseList(slow);
        while(newNode != null) {
            if(newNode.val != head.val) {
                return false;
            }
            head = head.next;
            newNode = newNode.next;
        }
        return true;
    }
    // 头插法，反转链表
    private ListNode reverseList(ListNode node) {
        ListNode newHead = null;
        ListNode p = node;
        // 反转后半段链表
        while(p != null) {
            ListNode tmp = p.next;
            p.next = newHead;
            newHead = p;
            p = tmp;
        }
        return newHead;
    }
}

328.奇偶链表（中等）

class Solution {
    public ListNode oddEvenList(ListNode head) {
        // 创建两个链表，一个只有奇数，一个只有偶数链表，遍历给定单链表，分别插入创建的链表，最终合并链表
        ListNode odd = new ListNode(), even = new ListNode(), res = odd, evenHead = even;
        int size = 1;
        while(head != null) {
            if(size % 2 != 0) {
                odd.next = head;
                odd = odd.next;
            } else {
                even.next = head;
                even = even.next;
            }
            head = head.next;
            size++;
        }
        odd.next = evenHead.next;
        even.next = null;
        return res.next;
    }
}

25. K个一组翻转链表（困难）

/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode(), p = head, tail = res;
        while(p != null) {
            int i = 1;
            ListNode tmpHead = p;
            // 1. 遍历k个结点，找到k范围内的头尾
            while(i < k && p != null) {
                p = p.next;
                i++;
            }
            if(p == null) {
                tail.next = tmpHead;
                return res.next;
            }
            ListNode tmp = p.next;
            ListNode[] resKGroup = reverse(tmpHead, p);
            tail.next = resKGroup[0];
            tail = resKGroup[1];
            p = tmp;
        }
        return res.next;
    }
    private ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode newHead = null, p = head;
        while(p != tail) {
            ListNode tmp = p.next;
            p.next = newHead;
            newHead = p;
            p = tmp;
        }
        tail.next = newHead;
        return new ListNode[] {tail, head};
    }
}

剑指Offer 22.链表中倒数第k个节点（简单）

遍历计算总数

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int size = 0;
        ListNode tmp = head; 
        while(tmp != null) {
            tmp = tmp.next;
            ++size;
        }
        for(int i = 0; i < size - k; i++) {
            head = head.next;
        }
        return head;
    }
}

快慢指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while(--k >= 0) {
            fast = fast.next;
        }
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

19.删除链表的倒数第N个结点（中等）

二次遍历

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        if(head == null) {
            return null;
        }
        int size = 0;
        ListNode tmp = head, res = head, pre = head;
        while(tmp != null) {
            tmp = tmp.next;
            size++;
        }
        for(int i = 0; i < size - n; i++) {
            pre = head;
            head = head.next;
        }
        if(res == head) {
            return head.next;
        }
        pre.next = head.next;
        return res;
    }
}

一次遍历-solution1

解题思路：

双指针

/**
* 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 removeNthFromEnd(ListNode head, int n) {
      if(head == null) {
          return null;
      }
      // 双指针
      ListNode first = head, second = head, res = head;
      while(n-- >= 0) {
          if(first == null) {
              return res.next;
          }
          first = first.next;
      }
      while(first != null) {
          first = first.next;
          second = second.next;
      }
      second.next = second.next.next;
      return res;
  }
}

一次遍历-solution2

解题思路：

双指针+哨兵节点简化编程

/**
* 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 removeNthFromEnd(ListNode head, int n) {
      ListNode dumyHead = new ListNode(-1, head);
      ListNode slow = dumyHead, fast = dumyHead;
      for(int i = 0; i < n; i++) {
          fast = fast.next;
      }
      while(fast != null && fast.next != null) {
          slow = slow.next;
          fast = fast.next;
      }
      slow.next = slow.next.next;
      return dumyHead.next;
  }
}

160.相交链表（简单）

快慢指针

解题思路：
A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点如果A,B不

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 错的人迟早会走散，而对的人迟早会相逢！
        // A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。 如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点 如果A,B不相交的话两个指针就会同时到达A+B（B+A）的尾节点
        if(headA == null || headB == null) {
            return null;
        }
        // 双指针
        ListNode heada = headA, headb = headB;
        while(heada != headb) {
            if(heada != null) {
                heada = heada.next;
            } else {
                heada = headB;
            }
            if(headb != null) {
                headb = headb.next;
            } else {
                headb = headA;
            }
        }
        return heada;
    }
}

141.环形链表（简单）

快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 链表判断是否存在环：快慢指针
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
}

栈和队列

剑指Offer 09.用两个栈实现队列（简单）

225.用队列实现栈（简单）

面试题03.05.栈排序（中等）

155.最小栈（简单）

面试题03.01.三合一（简单）

20.有效的括号（简单）

面试题16.26.计算器（中等）

772.基本计算器III（困难包含括号力扣会员）

1047.删除字符串中的所有相邻重复项（简单）

剑指Offer 31.栈的压入、弹出序列（中等）

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length != popped.length) {
            return false;
        }
        // 用数组 stack 模拟栈
        int[] stack = new int[pushed.length];
        int popIdx = 0, cur = 0;
        for(int i = 0; i < pushed.length; i++) {
            // stack 模拟入栈
            stack[cur] = pushed[i];
            // 当 stack 入栈的元素等于 出栈序列 poped 的当前元素时，对应出栈
            while(cur >= 0 && stack[cur] == popped[popIdx]) {
                // 模拟出栈操作
                cur--;
                popIdx++;
            }
            cur++;
        }
        // popped 序列对应的是栈的弹出顺序，那么模拟栈 stack 的下标应该等于 0
        return cur == 0;
    }
}

数组和链表

203.移除链表元素 （简单）

876.链表的中间结点（简单）

83.删除排序链表中的重复元素（简单）

剑指Offer 25.合并两个排序的链表 （中等）

2.两数相加 （中等）

206.反转链表 （中等）

递归

哨兵节点 + 头插法

234.回文链表 （中等）

328.奇偶链表（中等）

25. K个一组翻转链表（困难）

剑指Offer 22.链表中倒数第k个节点 （简单）

遍历计算总数

快慢指针

19.删除链表的倒数第N个结点 （中等）

二次遍历

一次遍历-solution1

一次遍历-solution2

160.相交链表（简单）

快慢指针

141.环形链表（简单）

快慢指针

栈和队列

剑指Offer 09.用两个栈实现队列（简单）

225.用队列实现栈（简单）

面试题03.05.栈排序（中等）

155.最小栈（简单）

面试题03.01.三合一（简单）

20.有效的括号（简单）

面试题16.26.计算器（中等）

772.基本计算器III（困难 包含括号 力扣会员）

1047.删除字符串中的所有相邻重复项（简单）

剑指Offer 31.栈的压入、弹出序列（中等）

739.每日温度（中等） 单调栈

42.接雨水（困难）单调栈

84.柱状图中最大的矩形（困难）单调栈

面试题03.06.动物收容所（中等） 队列

剑指Offer 59 - II.队列的最大值（中等） 单调队列

剑指Offer 59 - I.滑动窗口的最大值 （困难）单调队列

203.移除链表元素（简单）

剑指Offer 25.合并两个排序的链表（中等）

2.两数相加（中等）

206.反转链表（中等）

234.回文链表（中等）

剑指Offer 22.链表中倒数第k个节点（简单）

19.删除链表的倒数第N个结点（中等）

772.基本计算器III（困难包含括号力扣会员）

739.每日温度（中等）单调栈

面试题03.06.动物收容所（中等）队列

剑指Offer 59 - II.队列的最大值（中等）单调队列

剑指Offer 59 - I.滑动窗口的最大值（困难）单调队列