力扣刷题（第十六天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

删除排序链表中的重复元素

解题思路

本题要求删除排序链表中的重复元素，由于链表是有序的，所以重复的元素在链表中是连续出现的。我们可以通过遍历链表，比较当前节点的值和下一个节点的值，如果相等就跳过下一个节点，直到找到不相等的节点，然后将当前节点的next指针指向这个不相等的节点。

以下是具体步骤：

1. 判断链表是否为空：如果链表为空，直接返回None。
2. 遍历链表：使用一个指针current从链表的头节点开始遍历。
3. 比较相邻节点的值：在遍历过程中，比较current节点的值和current.next节点的值。如果相等，说明是重复元素，将current.next指向current.next.next，跳过重复节点；如果不相等，将current指针移动到current.next。
4. 返回头节点：遍历结束后，返回链表的头节点。

   # 定义链表节点类
   class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef deleteDuplicates(head):# 如果链表为空，直接返回 Noneif not head:return None# 初始化当前节点为头节点current = headwhile current.next:if current.val == current.next.val:# 如果当前节点的值和下一个节点的值相等，跳过下一个节点current.next = current.next.nextelse:# 如果不相等，移动到下一个节点current = current.nextreturn head# 辅助函数：将列表转换为链表
   def list_to_linked_list(lst):dummy = ListNode(0)current = dummyfor val in lst:current.next = ListNode(val)current = current.nextreturn dummy.next# 辅助函数：将链表转换为列表
   def linked_list_to_list(head):result = []current = headwhile current:result.append(current.val)current = current.nextreturn result# 测试代码
   input_list = [1, 1, 2, 3, 3]
   head = list_to_linked_list(input_list)
   new_head = deleteDuplicates(head)
   output_list = linked_list_to_list(new_head)
   print(output_list)    

逐行解释

# 定义链表节点类，每个节点包含一个值和一个指向下一个节点的指针
class ListNode:def __init__(self, val=0, next=None):# 节点的值self.val = val# 指向下一个节点的指针self.next = nextdef deleteDuplicates(head):# 如果链表为空，直接返回 Noneif not head:return None# 初始化当前节点为头节点，用于遍历链表current = head# 当当前节点有下一个节点时，继续遍历while current.next:# 如果当前节点的值和下一个节点的值相等if current.val == current.next.val:# 跳过下一个节点，将当前节点的 next 指针指向下下个节点current.next = current.next.nextelse:# 如果不相等，将当前节点移动到下一个节点current = current.next# 遍历结束后，返回链表的头节点return head# 辅助函数：将列表转换为链表
def list_to_linked_list(lst):# 创建一个虚拟头节点，方便操作dummy = ListNode(0)# 初始化当前节点为虚拟头节点current = dummy# 遍历列表中的每个元素for val in lst:# 创建一个新节点，值为当前元素current.next = ListNode(val)# 将当前节点移动到新节点current = current.next# 返回虚拟头节点的下一个节点，即链表的头节点return dummy.next# 辅助函数：将链表转换为列表
def linked_list_to_list(head):# 用于存储链表元素的列表result = []# 初始化当前节点为链表的头节点current = head# 当当前节点不为空时，继续遍历while current:# 将当前节点的值添加到结果列表中result.append(current.val)# 将当前节点移动到下一个节点current = current.next# 返回结果列表return result# 测试代码
# 定义一个包含重复元素的列表
input_list = [1, 1, 2, 3, 3]
# 将列表转换为链表
head = list_to_linked_list(input_list)
# 调用 deleteDuplicates 函数删除重复元素
new_head = deleteDuplicates(head)
# 将处理后的链表转换为列表
output_list = linked_list_to_list(new_head)
# 打印处理后的列表
print(output_list)