基本概念

栈：先进后出

  • 栈顶，栈底，进栈，出栈
  • 实现方式：顺序栈（数组），链栈（链表）

    两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表

  • 应用：浏览器的回退（page.history），IDE的括号匹配
  • 相关题目：虽然栈的运作机制很简单实现功能也较少，但由于不同于其他结构的先进后出的结构，通过主栈加辅栈的组合也能实现不错的功能
    • 剑指09. 用两个栈实现一个队列
    • 剑指30. 包含min函数的栈

队列：先进先出

  • 实现方式：
    1. 列表：list和list.pop(0)
    2. python库：collections.dqueue和dqueue.popleft()

      时间复杂度的不同：list 是列表，数组移除头部元素的方式是把后面的元素全部往前移动一位，所以复杂度是 O(N) ； deque 是双端队列，底层是链表，因此头部和尾部是等价的，插入删除都是 O(1)

  • 应用：遍历树或图时
  • 相关题目：

链表

  • 相关题目：
    • 利用链表有序的特点进行遍历：
      • 剑指16. 从尾到头打印链表
      • 剑指18. 删除链表的节点
    • 但是也因为有序的特点，如果我们想翻转链表的顺序时就变得麻烦；我们可以使用最常见的遍历改变节点间的指向，也可以使用递归进行反向操作，或者利用特殊的双指针模式避免逆序操作。
      • 剑指24. 翻转链表（中转+递归）
      • 剑指22. 链表中倒数第k个字节（快慢指针）

剑指09. 用两个栈实现一个队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路：

两个栈，一个主要，一个辅助。添加时可以直接用append实现末尾添加。删除时需要把主栈元素倒回辅助，删掉第一个，再倒回来。

复杂度

  • 删除：空间O(n), 时间O(n)
  • 插入：空间O(1), 时间O(1)
## 注意题目要求：两个栈
class CQueue(object):

    def __init__(self):
        self.stack1 = [] ##主队列
        self.stack2 = [] ##辅助

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack1.append(value)

    def deleteHead(self):
        """
        :rtype: int
        """
        if self.stack1:
            ## 取出
            for i in range(len(self.stack1)-1):
                self.stack2.append(self.stack1.pop())
            deleted = self.stack1.pop()

            ## 放回stack1
            while self.stack2 :
                self.stack1.append(self.stack2.pop())

        else:
            return -1

        return deleted

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

剑指30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)

解题思路：

  • 栈的特性：top没有出来之前，下面的是一定存在的。换言之，当top在的时候，对应的当前栈的最小值是不会变的。
  • 创建动态储存最小值的辅助栈。push的时候对比上一个最小值和当前input，将小的push进辅助栈。pop的时候一并pop辅助
  • 为避免第一个push时out of index，初始化辅助栈时先加入一个无穷大(math.inf)

Tip

  1. python数组索引可以通过负值来倒着取出
  2. 栈顶是指最后一个进来的
  3. list.pop()默认pop最后一位
class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = [math.inf]

    def push(self, x) -> None:
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        
        if x < self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        """
        :rtype: None
        """
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        """
        :rtype: int
        """
        result = self.stack[-1]
        return result

    def min(self) -> int:
        """
        :rtype: int
        """
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

剑指16. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解题思路：

用list顺序存储单向链表，使用切片直接倒序输出。

Tip：

  • 列表切片规则List[start:stop:step]，不加则是默认全部区间
  • List[::-1]则代表倒置列表

复杂度

  • 时间O(n)， 空间O(n)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        result = []

        while head:
            result.append(head.val)
            head = head.next

        return result[::-1]

剑指24. 翻转链表（中转+递归）

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解题思路：
需要解决的问题其实有两个：1. 如何改变node之间的指向 2. 如何保存头部节点

  1. 使用中转点对上一个node保存，遍历链表同时改变指向，最后一个到达的就是新链表的头部节点
  2. 递归。只有到达最后一个节点后才开始进行翻转。这里通过返回值不停传递末节点，即新链表的头结点。
    • 传递参数：当前节点和下一节点
    • 停止条件：当前节点为空
    • 返回值：上一节点
    • 执行动作：将下一节点指向当前节点

复杂度

  • 时间：O(n)，空间：O(2)

中转站法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prevNode = None

        while head:
            head.next = prevNode
            prevNode = head
            head = head.next

        return prevNode
  • 时间：O(n)，
  • 空间：O(n):递归深度达到n，需要n的空间

递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recur(cur: ListNode, prev: ListNode) -> ListNode:

            ## 迭代中止：到达最后一个Node的时候next会变成None，这时返回最后一个Node
            ## 最后一个Node会变成新链表的head，使用变量进行保存
            if cur:
                head = recur(cur.next, cur)
                cur.next = prev
                return head
            else:
                return prev

        return recur(head, None)

剑指18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

时间O(n)， 空间O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head : return head
        if head.val == val : return head.next

        result = head 

        while 1 :
            if head.next.val == val :
                head.next = head.next.next
                break
            head = head.next

        return result

剑指22. 链表中倒数第k个字节（快慢指针）

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

遍历法很容易想到就不在这里赘述了

  • 时间O(n) 空间O(1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow, fast = head, head

        for _ in range(k-1) :
            fast = fast.next

        while head and fast.next :
            slow = slow.next
            fast = fast.next

        return slow

剑指25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

  • 善用伪头结点可以减少很多步骤，如判断哪个才是头结点造成的代码行数增加
  • 因为是链表结构而非数组，因此不用考虑最后剩下的需要用while再一个个塞进去
  • 时间O(n)， 空间O(1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:  
        head = ListNode(0)
        cur = head

        while l1 and l2 :
            if l1.val <= l2.val :
                cur.next, l1 = l1, l1.next
            else :
                cur.next, l2 = l2, l2.next
            cur = cur.next
        
        if l1 :
            cur.next = l1
        if l2 :
            cur.next = l2