1. 题目：反转链表
问题描述： 给定一个单链表的头节点 head，将该链表反转，并返回反转后的头节点。
示例：
rust
Copy code
输入：1 -> 2 -> 3 -> 4 -> 5 -> NULL
输出：5 -> 4 -> 3 -> 2 -> 1 -> NULL
解决方法：
反转链表是一个经典的链表操作问题。可以使用迭代 英国电话号码 或递归两种方法来解决。
迭代方法： 使用三个指针分别指向当前节点、前一个节点和后一个节点，依次调整指针的方向，直到链表全部反转完成。
python
Copy code
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseLinkedList(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
递归方法： 递归地反转链表的子部分，然后调整指针指向，直到整个链表反转完成。
python
Copy code
def reverseLinkedListRecursive(head):
if not head or not head.next:
return head
new_head = reverseLinkedListRecursive(head.next)
head.next.next = head
head.next = None
return new_head
2. 题目：有效的括号
问题描述： 给定一个只包含字符 '('，')'，'{'，'}'，'[' 和 ']' 的字符串 s，判断字符串是否有效。有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例：
graphql
Copy code
输入：s = "()[]{}"
输出：True
输入：s = "([)]"
输出：False
解决方法：
使用栈来解决有效括号问题是非常直观和高效的方法。
python
Copy code
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
3. 题目：最小栈
问题描述： 设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
示例：
scss
Copy code
输入：
操作：push(-2), push(0), push(-3), getMin, pop, top, getMin
输出：[-3, 0, -2]
解决方法：
使用辅助栈来实现最小栈，辅助栈存储当前栈中的最小元素。
python
Copy code
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
结语
以上是几个常见的数据结构题目及其解决方法。在面试准备过程中，掌握这些经典问题的解法不仅有助于理解数据结构的应用，也能够提升解决问题的能力和效率。通过实际练习和深入理解，可以更好地应对各种数据结构相关的面试挑战，展现出自己的技术实力和潜力。