leetcode-4.27[83. 删除排序链表中的重复元素、100. 相同的树]（python解法）

题目1 原创文章 80获赞 39访问量 3万+ 关注 私信 展开阅读全文 作者：Leadingme 【题目1 - 83. 删除排序链表中的重复元素】 在本题中，我们面临的是一个关于链表处理的问题。给定一个已排序的链表，我们的任务是删除所有重复的元素，使得每个元素只出现一次。链表节点定义如下： ```python class ListNode: def __init__(self, x): self.val = x self.next = None ``` 解决这个问题的关键在于，由于链表是有序的，我们可以使用两个指针，一个快指针`fast`和一个慢指针`slow`。初始时，`slow`指向头节点，`fast`指向`slow`的下一个节点。我们遍历链表，如果`fast`指针所指向的节点值与`slow`指针相同，那么就将`fast`移动到下一个节点；如果不同，我们就将`slow`指针的`next`更新为`fast`当前的值，然后同时移动`slow`和`fast`到下一个节点。这样，`slow`指针始终指向新链表的最后一个元素，而`fast`则用于探测是否存在重复。当`fast`到达链表尾部时，`slow`指针所在的位置就是新链表的尾部。 以下是Python实现代码： ```python def deleteDuplicates(head): if not head or not head.next: return head slow = head fast = head.next while fast: if fast.val != slow.val: slow.next = fast slow = slow.next fast = fast.next slow.next = None return head ``` 【题目2 - 100. 相同的树】 此题考察的是二叉树的比较。给定两棵二叉树，我们需要判断它们是否完全相同，即结构和每个节点的值都完全一致。二叉树节点的定义如下： ```python class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None ``` 解决这个问题可以采用递归的方法。我们首先比较两棵树的根节点值，如果值不相同，那么显然两棵树不同；如果相同，我们继续分别比较左右子树。这里需要注意，即使两棵树的根节点值相同，但若左右子树不相同，那么这两棵树也不相同。因此，我们递归地对左右子树进行相同性检查。 以下是Python实现代码： ```python def isSameTree(p, q): if p is None and q is None: return True elif (p is None) ^ (q is None) or p.val != q.val: return False else: return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) ``` 总结来说，这两个题目分别涉及到链表操作和二叉树的比较，都是数据结构和算法的经典问题。对于链表问题，利用双指针可以有效地处理有序链表的重复元素；而对于二叉树问题，递归策略是解决这类问题的有效工具。通过熟练掌握这些基本算法，可以为后续的编程挑战打下坚实基础。