大厂常考题：数据结构与算法之链表操作与树结构总结
在面试中，数据结构与算法是考察程序员基本功的重要环节。链表和树结构作为数据结构中的两种重要类型，经常出现在各大厂的面试题中。本文将围绕链表操作和树结构，总结一些常见的大厂面试题，并给出相应的代码实现。
链表操作
链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表操作包括插入、删除、查找等。
1. 反转链表
题目描述：给定一个单链表的头节点，反转该链表。
思路：使用三个指针，分别指向当前节点的前一个节点、当前节点和下一个节点，通过修改指针的指向来实现链表的反转。
代码实现：
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
2. 合并两个有序链表
题目描述：给定两个有序链表的头节点，合并它们为一个新的有序链表。
思路：使用两个指针分别遍历两个链表，比较当前节点值的大小，将较小的节点添加到新链表中，并移动指针。
代码实现：
python
def merge_two_lists(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
3. 删除链表的倒数第N个节点
题目描述：给定一个链表和一个整数N，删除链表的倒数第N个节点。
思路：使用两个指针，一个指针先走N步，然后两个指针同时移动，当先走的指针到达链表末尾时，后走的指针指向的节点即为倒数第N个节点。
代码实现：
python
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
树结构
树是一种非线性数据结构，由节点组成，每个节点有零个或多个子节点。树结构包括二叉树、二叉搜索树、平衡树等。
1. 二叉树遍历
二叉树遍历包括前序遍历、中序遍历和后序遍历。
前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。
代码实现：
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root):
if root:
print(root.val, end=' ')
preorder_traversal(root.left)
preorder_traversal(root.right)
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=' ')
inorder_traversal(root.right)
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=' ')
2. 二叉搜索树
二叉搜索树（BST）是一种特殊的二叉树，满足以下性质：
- 左子树上所有节点的值均小于它的根节点的值。
- 右子树上所有节点的值均大于它的根节点的值。
- 左、右子树也分别为二叉搜索树。
插入节点：
python
def insert_into_bst(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_into_bst(root.left, val)
else:
root.right = insert_into_bst(root.right, val)
return root
查找节点：
python
def search_in_bst(root, val):
if root is None or root.val == val:
return root
if val < root.val:
return search_in_bst(root.left, val)
return search_in_bst(root.right, val)
3. 平衡二叉树
平衡二叉树（AVL树）是一种自平衡的二叉搜索树，满足以下性质：
- 每个节点的左右子树的高度差不超过1。
旋转操作：
- 左旋：将当前节点作为右子节点的左子节点。
- 右旋：将当前节点作为左子节点的右子节点。
代码实现：
python
def rotate_left(root):
new_root = root.right
root.right = new_root.left
new_root.left = root
return new_root
def rotate_right(root):
new_root = root.left
root.left = new_root.right
new_root.right = root
return new_root
def insert_into_avl(root, val):
if root is None:
return TreeNode(val)
if val < root.val:
root.left = insert_into_avl(root.left, val)
else:
root.right = insert_into_avl(root.right, val)
更新节点高度
root.height = 1 + max(get_height(root.left), get_height(root.right))
获取平衡因子
balance_factor = get_balance(root)
左左情况
if balance_factor > 1 and val < root.left.val:
return rotate_right(root)
右右情况
if balance_factor < -1 and val > root.right.val:
return rotate_left(root)
左右情况
if balance_factor > 1 and val > root.left.val:
root.left = rotate_left(root.left)
return rotate_right(root)
右左情况
if balance_factor < -1 and val < root.right.val:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
def get_height(root):
if root is None:
return 0
return 1 + max(get_height(root.left), get_height(root.right))
def get_balance(root):
if root is None:
return 0
return get_height(root.left) - get_height(root.right)
总结
本文总结了链表操作和树结构中的一些常见大厂面试题，并给出了相应的代码实现。掌握这些数据结构与算法，对于提高面试成功率具有重要意义。在实际面试中，除了掌握算法本身，还需要注意代码的可读性和效率。希望本文能对您的面试准备有所帮助。
Comments NOTHING