在备战考研数据结构时，以下是一些必背的代码示例，涵盖了常见的算法和数据结构操作：
1. 链表操作：
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True 循环存在
return False 无循环
```
2. 栈与队列操作：
```python
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
```
3. 树和二叉树操作：
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val)
inorder_traversal(root.right)
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = build_tree(preorder[1:mid+1], inorder[:mid])
root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
return root
```
4. 查找和排序算法：
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
```
微信小程序：【考研刷题通】——你的考研刷题利器！涵盖政治、英语、数学等全部考研科目，海量真题、模拟题，助你高效备考，轻松上研！立即体验，开启你的考研刷题之旅！【考研刷题通】