中级面试题
队列和栈的区别
面试题目
请说明队列和栈的区别
公司
- 字节跳动
招聘类型
- 社招
- 校招
答案
队列（Queue）和栈（Stack）是两种常见的数据结构，它们在数据存储和访问方面有着不同的特点。以下是它们之间的主要区别：
- 数据结构特性：
- 队列是一种先进先出（First In, First Out，FIFO）的数据结构，类似于排队，即最先进入队列的元素最先被移出。
-
栈是一种后进先出（Last In, First Out，LIFO）的数据结构，类似于堆叠，即最后压入栈的元素最先被弹出。
-
操作：
- 队列支持两种主要操作：入队（enqueue）和出队（dequeue）。元素从队列尾部入队，从队列头部出队。
-
栈支持两种主要操作：压栈（push）和弹栈（pop）。元素从栈顶压入栈中，从栈顶弹出栈。
-
应用场景：
- 队列常用于需要按照先后顺序处理数据的场景，如任务调度、消息队列等。
-
栈常用于需要后进先出顺序访问数据的场景，如表达式求值、函数调用栈等。
-
内存管理：
- 队列和栈都可以通过数组或链表来实现。在使用数组实现时，队列的头部和尾部分别用于出队和入队操作；而栈只需操作数组的尾部即可。
- 在使用链表实现时，队列和栈的实现方式会有所不同。队列通常使用单向链表，头部用于出队，尾部用于入队；而栈通常使用单向链表或双向链表，头部用于压栈和弹栈操作。
总的来说，队列和栈是两种常用的数据结构，它们分别适用于不同的场景和需求，对于数据的存储和访问提供了不同的解决方案。
链表反转
面试题目
请编写一下链表反转算法。
公司
- 阿里巴巴
招聘类型
- 社招
- 校招
答案
迭代解法
def reverseList(self, head: ListNode) -> ListNode:
prev, curr = None, head
while curr is not None:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
递归解法
def reverseList(self, head: ListNode) -> ListNode:
# 1. 递归终止条件
if head is None or head.next is None:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p