链表是按照先后顺序排列的一种数据结构，这里我们以单链表为例，笔者头一次刷力扣时，不懂链表是怎么来的，这里需要补充介绍一些基础的知识，帮助读者理解链表题。
链表节点
单链表结点的定义式非常简洁，我们这里用一个类进行定义，这个类有两个实例变量：
- 该结点的值（val），可能是一个整数，也可以是其他的数据结构；
- 该结点所指的下一个结点（next），也是一个结点。
如果是双链表，那么还会有前一个结点（prev），可以指向前一个节点。
class ListNode:
"""
链表节点
"""
def __init__(self, x): # 在创建结点时，执行初始化赋值程序
self.val = x # 当前结点的值
self.next = None # 下一个节点，刚创建时为None
链表创建
链表是由结点组成的，链表是结点的联结，因此链表的创建包括结点的创建和结点的连接两个步骤。
def create_linked_list(nums):
"""
创建链表
:param nums: 输入代表里链表的数字列表
:return: 返回创建好的链表的头结点，可以得到整个链表的所有信息
"""
if not nums: # 输入空列表
return
head = prev = ListNode(nums[0]) # 第一个结点
for num in nums[1:]:
tmp = ListNode(num) # 创建当前结点
prev.next = tmp # 挂在已经创建好的链表末尾
prev = prev.next # 指针后移
return head
链表复制
链表复制，相当于在创建链表时用另一个链表约束创建过程。链表复制相当于链表的浅拷贝，在链表题目中可以避免链表进入函数后被修改等情况。
def copy_linked_list(head):
"""
把链表复制一份，且不改变原链表结构
:param head:
:return:
"""
new_head, cur = ListNode(0), head # 新链表的准头结点，原来链表的当前结点
tmp = new_head # 临时结点
while cur: # 当前结点不为空
new_cur = ListNode(cur.val) # 根据原链表当前结点构造新的当前结点
tmp.next = new_cur # 新结点连接到已完成的部分末尾
cur = cur.next # 当前结点后移
tmp = tmp.next # 新链表末尾后移
return new_head.next # 返回新链表
链表打印
如果得到一个链表的起始结点，那么相当于获得了整个链表的所有结点的所有值。
def print_linked_list(head):
"""
打印链表
:param head: 要打印的链表的头结点
:return: 结点值列表
"""
tmp = head # 临时变量
nums = []
while tmp:
nums.append(tmp.val)
tmp = tmp.next
print(nums)
return nums
上面的办法只能判别链表不是环形链表的情况，如果链表存在环形结构，程序就会陷入死循环，我们改写了进阶版本的程序，可以判别环形链表。
def print_linked_list(head):
"""
打印链表
:param head: 要打印的链表的头结点
:return: 结点值列表
"""
cur = head # 为了不改变输入，使用临时变量
nums = [] # 结果数组
nodes = []
circle_flag = False # 是否为环形链表的flag
circle_nums = [] # 环形区域的结果
while cur:
nodes.append(cur)
if circle_flag:
circle_nums.append(cur.val) # 添加环形区域的元素
else:
nums.append(cur.val)
cur = cur.next
if cur in nodes:
if nodes.count(cur) == 2: # 第二次进入环形区
break
else: # 首次进入环形区，修改环形flag
circle_flag = True
if circle_flag:
print("当前链表是环形链表")
print("链表中的元素为：{}".format(nums))
print("环形区的元素为：{}".format(circle_nums))
print("入口元素为：{}".format(nums[len(nums)-len(circle_nums)]))
else:
print("链表中的元素为：{}".format(nums))
return nums
例如，当我们执行以下代码时：
if __name == '__main__':
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next = n2
n2.next = n3
n3.next = n4
print_linked_list(n1)
会得到打印的结果：
链表中的元素为：[1, 2, 3, 4]
如果构造环形链表，在刚才代码的基础上增加一句话：
if __name == '__main__':
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n2 # 加的那句话
print_linked_list(n1)
会得到打印的结果：
当前链表是环形链表
链表中的元素为：[1, 2, 3, 4]
环形区的元素为：[2, 3, 4]
入口元素为：2
链表判等
链表判等，判断链表相应元素的值是否相等即可。
def list_equal(head1, head2):
"""
判断两个链表是否相等
:param head1:
:param head2:
:return:
"""
cur1, cur2 = head1, head2 # 为了不改变输入，均使用临时变量
tmp = head1 # 用于判断环形链表
while cur1 and cur2:
if cur1.val != cur2.val:
return False
cur1, cur2 = cur1.next, cur2.next
if cur1 == tmp:
return True
return not cur1 and not cur2
链表判环
如果链表存在环形结构，那么在遍历时一定会遇到曾经遍历过的结点，否则一定会遍历到末尾结点。
def is_circle(head):
"""
判断链表是否是环形链表
:param head: 要判断的链表的头结点
:return: 布尔量，判断结果
"""
if not head:
return False
tmp = head
while head:
head = head.next
if not head: # 遍历到了链表末尾
return False # 链表不是环形结点
if head == tmp: # 遍历到了之前遍历过的结点
return True # 链表是环形结点
如有疑问或建议，欢迎评论区留言~
网友评论