数据结构与算法（四）：Python实现单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串
根据链表数据结构的知识，进行初步练习，从单链表的反转、环的检测、两个有序链表的合并、判断单向链表是否是回文字符串四个题目着手，分别进行代码实现。
首先定义单链表类：
# 结点类
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
# 单链表类
class SinglyLinkedList(object):
def __init__(self):
self.head = None
self.length = 0
# 从一个列表创建单链表
def crt_from_list(self, L):
L.reverse()
for l in L:
self.head = Node(l, next=self.head)
self.length += 1
# 单链表遍历
def lineprint(self):
if not self.head:
print("NULL")
return
p = self.head
print(p.data)
while p.next:
print(p.next.data)
p = p.next
一、单链表反转
def ll_reverse(L:SinglyLinkedList):
"""
先找到尾部结点，然后从头结点开始，依次插入尾部结点指针之后。
"""
head = L.head
tail = L.head
while tail.next:
tail = tail.next
while head != tail:
L.head = head.next
head.next = tail.next
tail.next = head
head = L.head
return L
二、单链表环的检测
def is_loop(L:SinglyLinkedList):
"""
链表中环的检测: 检测一个是否存在环
方法：
使用快慢指针（分别设为quick,slow），从head开始跑，quick步长为2，slow步长为1，分几种情况：
无环：快指针quick的next或者next.next为None，也即快指针quick走到了尾部；
有环：快指针quick的next或者next.next指向了慢指针slow；
"""
if L.head is None or L.head.next is None:
return False
quick, slow = L.head.next, L.head
while 1:
if quick == slow or quick.next == slow:
return True
elif quick is None or quick.next is None:
return False
slow = slow.next
quick = quick.next.next
三、两个有序的链表合并
def merge_of_2_ll(L1:SinglyLinkedList,L2:SinglyLinkedList):
"""
有序分几种情况：正序-正序、正序-逆序、逆序-正序、逆序-逆序，这里仅考虑“正序-正序”的情况。
方法：
以第一个链表为基础，先构造一个哨兵结点，然后将第二个链表中的节点依次插入第一个链表；
由于是两个有序链表，所以插入时只需在上次插入点之后查找即可；
"""
if not L1.head:
return L2
elif not L2.head:
return L1
# 对L1构造哨兵结点，加在其头部之前
L0 = SinglyLinkedList()
L0.crt_from_list(L=[0])
L0.head.next = L1.head
p1, p2 = L0.head, L2.head
# 对L2链表中的节点，依次插入到L1
while p2:
L2.head = L2.head.next
# 如果当前p1.next不为空，则向后遍历：
while p1.next and p1.next.data<=p2.data:
p1 = p1.next
# 将当前p2插入其后
p2.next = p1.next
p1.next = p2
p1 = p1.next
# 更新p2
p2 = L2.head
return L1
四、判断单向链表是否是回文字符串
def is_plalidrome(L):
if not L.head:
return False
"""
1、先利用慢、快两个指针找到链表中心点，分两种情况：
偶数序列：当快指针到达末尾节点时，慢指针指向中间偏后那个节点；
奇数序列：当快指针到达末尾节点时，慢指针指向中间节点；
"""
p1, p2 = L.head, L.head
flag = 1
while p2.next:
p1 = p1.next
if p2.next.next:
p2 = p2.next.next
else:
p2 = p2.next
flag = 2
break
print("奇数序列") if flag==1 else print("偶数数序列")
print("找到中点时，p1,p2指向节点的值：",p1.data, p2.data)
"""
2、再从慢指针开始：
将慢指针指向的节点依次插入快指针后面，从而形成后半部分链表反转
"""
while p1 != p2:
p3 = p1.next
p1.next = p2.next
p2.next = p1
p1 = p3
print("逆序完成时，p1,p2指向节点的值：",p1.data, p2.data)
"""
3、开始比对:从原始链表的表头和p1开始一一比对，直到其中之一为空
"""
while L.head and p1:
if L.head.data != p1.data:
print("Is not plalindrome")
return False
L.head = L.head.next
p1 = p1.next
print("Is plalindrome")
return True
作者：叶舟
