赞
踩
许多小伙伴在刷题时会涉及到链表排序,但对于只学习Python的小伙伴,对于链表的数据结构不太熟悉,无法有效理解ListNode的定义及使用。读者在进行LeetCode刷题时也懵懵懂懂,今天就在这里彻底搞清楚。
- class ListNode:
- def __init__(self, x):
- self.val = x
- self.next = None
'运行
说明:上述代码定义了一个名为 ListNode
的类,它是链表中的一个节点的表示。在链表数据结构中,每个节点通常包含两部分:一个存储数据的值(通常是一个整数、字符或其他数据类型),以及一个指向下一个节点的指针。
class ListNode:
这行定义了一个名为ListNode
的新类。def __init__(self, x):
这是ListNode
类的初始化方法(也称为构造函数)。当你创建一个新的ListNode
对象时,这个方法会被自动调用。它接受两个参数:self
和x
。self
是一个对实例本身的引用,而x
是我们要存储在节点中的值。self.val = x
:这行将传入的参数x
的值赋给self.val
。这意味着每个ListNode
对象都有一个val
属性,用于存储节点的值。self.next = None
:这行初始化self.next
属性为None
。self.next
是一个指向下一个ListNode
对象的指针。在创建新的节点时,我们不知道它的下一个节点是什么,所以我们将它初始化为None
。当我们构建链表时,我们会根据需要更新这个指针。
例:构建一个链表:3->5->6->1
- # 创建各个节点
- node3 = ListNode(3)
- node5 = ListNode(5)
- node6 = ListNode(6)
- node1 = ListNode(1)
-
- # 构建链表
- node3.next = node5
- node5.next = node6
- node6.next = node1
-
- # 链表构建完成,现在 node3 是链表的头节点
- head = node3
-
- # 打印链表以验证
- current_node = head
- while current_node:
- print(current_node.val, end='->')
- current_node = current_node.next
- print('None') # 打印链表的结尾
题1:使用链表ListNode,将给定的链表排序
- def insertion_sort_list(head):
- # 如果链表为空或只有一个节点,则无需排序
- if not head or not head.next:
- return head
-
- # 创建一个哑节点(dummy node)作为新链表的头部
- dummy = ListNode(0)
- dummy.next = head
- current = head
-
- while current and current.next:
- # 如果当前节点的值小于下一个节点的值,则无需交换
- if current.val <= current.next.val:
- current = current.next
- continue
-
- # 否则,需要找到正确的位置插入当前节点
- prev = dummy
- while prev.next and prev.next.val < current.val:
- prev = prev.next
-
- # 将当前节点从原链表中移除
- next_node = current.next
- current.next = next_node.next
-
- # 将当前节点插入到正确的位置
- next_node.next = prev.next
- prev.next = next_node
-
- # 检查是否还需要对刚刚移动过的节点进行进一步排序
- current = prev.next
-
- # 返回排序后的链表
- return dummy.next
'运行
题2:将两个有序链表合并为一个有序链表(升序)
- def mergeTwoLists(l1, l2):
- # 创建一个移动点和头节点
- curr = dummy = ListNode(0)
-
- # 移动节点,比较两个链表的值大小
- while l1 and l2:
- if l1.val < l2.val:
- curr.next = l1
- l1 = l1.next
- else:
- curr.next = l2
- l2 = l2.next
- curr = curr.next
- # 当其中一个链表移动完时,将另一个链表剩余的节点拼接即可
- curr.next = l1 or l2
-
- return dummy.next
'运行
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。