在计算机科学中，数据结构是组织和存储数据的方式，它直接影响算法的效率和性能。掌握好数据结构对于编写高效的程序至关重要。下面是一些常见的数据结构练习题，帮助大家巩固基础知识。
1. 链表反转
问题描述：
给定一个单链表，请反转链表并返回新的头节点。
示例：
输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 5 -> 4 -> 3 -> 2 -> 1
解法思路：
可以使用迭代的方法来实现链表的反转。定义三个指针：prev、curr和next。初始时，prev为null，curr指向头节点。每次迭代时，先保存curr.next到next，然后将curr.next设置为prev，接着移动prev到curr，curr到next。重复此过程直到curr为null。
```python
def reverse_list(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
```
2. 栈与队列的应用
问题描述：
设计一个支持 push、pop、top 操作，并能在常数时间复杂度内获取栈的最小元素 min() 的栈。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top();// 返回 0
minStack.getMin(); // 返回 -2
解法思路：
可以通过维护两个栈来解决这个问题。一个栈用于正常的push和pop操作，另一个栈用于记录当前栈中的最小值。每次push时，如果新元素小于或等于辅助栈的栈顶元素，则也push到辅助栈；每次pop时，如果pop出的元素等于辅助栈的栈顶元素，则也从辅助栈中pop。
```python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x):
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
```
3. 二叉树遍历
问题描述：
给定一棵二叉树，返回其前序遍历的结果。
示例：
输入: [1,null,2,3]
输出: [1,2,3]
解法思路：
前序遍历是指先访问根节点，然后遍历左子树，最后遍历右子树。可以使用递归或者迭代的方法实现。
递归方法：
```python
def preorderTraversal(root):
res = []
def dfs(node):
if node:
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
```
迭代方法：
```python
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
总结
以上是一些基础的数据结构练习题及其解法。通过不断练习这些题目，可以帮助我们更好地理解和掌握数据结构的核心概念。希望这些题目能够帮助你在学习数据结构的过程中有所收获！
