1. 定义
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
1.1 遍历链表
def bian_li(head):
if not head:
print("list is null")
return
p = head.next
while p:
print(p.val)
p = p.next
1.2 求表长
def get_length(head):
if not head:
return -1
cnt = 0
p = head.next
while p:
cnt += 1
p = p.next
return cnt
1.3 删除一个结点
def delete_node(head, node):
if not head:
return None
if not node:
return head
p = head
while p.next != node:
p = p.next
p.next = node.next
return head
1.4 求链表中间结点
链表中间结点即链表长度一半位置处的结点 （L//2+1）
使用快慢指针，当快指针遍历到链尾时，慢指针所指即为中间结点。
def get_mid(head):
if not head:
return None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
1.5 测试
# 定义结点
head = ListNode(-1)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
# 构造链表
head.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
# ---------求表长--------
print(get_length(head))
# 4
# ---------删除表结点--------
delete_node(head, n2)
bian_li(head)
# 1 3 4
# ---------求链表中间结点--------
print(get_mid(head).val)
# 2
2. 链表反转
时间复杂度o(n)
2.1 递归
2.2 头插法（使用三个指针）
def reverse(head):
if not head:
return None
# 已反转新链表的首结点
pre = None
# 下一个待反转的结点
next = None
# 当前待反转的结点
head = head.next
while head:
# 保存下一个待反转的结点
next = head.next
# 采用头插法，每次插入pre之前
head.next = pre
# pre 再次移动到已反转新链表的首位
pre = head
# 当前待反转结点后移
head = next
# 给反转后的新链表加一个头结点
temp = ListNode(-1)
temp.next = pre
return temp
2.3 借助栈
def reverse1(head):
if not head:
return head
stack = []
p = head.next
while p:
stack.append(p)
p = p.next
# 新链表头结点
new_head = ListNode(-1)
temp = new_head
while stack:
temp.next = stack.pop()
temp = temp.next
# 设置最后一个结点的next
temp.next = None
return new_head
2.4 测试
new_head = reverse(head)
bian_li(new_head)
# 4 3 2 1
new_head1 = reverse1(head)
bian_li(new_head1)
# 4 3 2 1
3. 链表合并
3.1 合并两个排序链表
def merge_sort_list(head1, head2):
if not head1:
return head2
if not head2:
return head1
# 默认链表带头结点
p1, p2 = head1.next, head2.next
# 新链表的头结点
head = ListNode(-1)
p3 = head
while p1 and p2:
if p1.val <= p2.val:
p3.next = p1
p1 = p1.next
else:
p3.next = p2
p2 = p2.next
p3 = p3.next
if p1:
p3.next = p1
if p2:
p3.next = p2
return head
3.2 测试
head1 = ListNode(-1)
head2 = ListNode(-1)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
head1.next = n1
n1.next = n3
n3.next = n5
head2.next = n2
n2.next = n4
new_head = merge_sort_list(head1, head2)
bian_li(new_head)
# 1 2 3 4 5
4. 结点查找
4.1 链表倒数第K个结点
使用两个指针，first先走k-1步，然后last再走。
def lastK(head, k):
if not head or k < 1:
return None
first = last = head
while k != 0 and first:
k -= 1
first = first.next
# k>链表长度
if not first:
return -1
while first:
first = first.next
last = last.next
return last.val
4.2 测试
head = ListNode(-1)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
head.next = n1
n1.next = n3
n3.next = n5
print(lastK(head, 3))
# 1
|