"""
给定链表L0->L1->L2...Ln-1->Ln, 把链表从新排序为L0->Ln->L1->Ln-1->L2...。要求：（1）在原来链表的基础上进行排序，既不能申请新的结点；（2）只能修改结点的next域，不能修改数据域
"""
class LNode:
def __init__(self):
self.data = None
self.next = None
def FindMiddleNode(head):
'''
方法功能：找到链表Head中间结点，把链表从中间断成两个子链表
:param head: 链表头结点
:return: 链表中间结点
'''
if head is None or head.next is None:
return head
fast = head # 遍历链表的时候每次向前走2步
slow = head # 遍历链表的时候每次向前走1步
slowPre = head
# 当fast到链表尾时候，slow刚好指向链表的中间结点
while fast is not None and fast.next is not None:
slowPre = slow
slow = slow.next
fast = fast.next.next
# 把链表断开成两个独立的子链表
slowPre.next = None
return slow
def Reverse(head):
'''
方法功能：对不带头结点的单链表翻转
:param head: 链表头结点
:return:
'''
if head is None or head.next is None:
return head
pre = head # 前驱结点
cur = head.next # 当前结点
next = cur.next # 后继结点
pre.next = None
# 使当前遍历到的结点cur指向其前驱结点
while cur is not None:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
def Recorder(head):
'''
方法功能：对链表进行拍戏
:param head: 链表头结点
:return:
'''
if head is None or head.next is None:
return
# 前半部分链表第一个结点
cur1 = head.next
mid = FindMiddleNode(head.next)
# 后半部分链表逆序后的第一个结点
cur2 = Reverse(mid)
tmp = None
# 合并两个链表
while cur1.next is not None:
tmp = cur1.next
cur1.next = cur2
cur1 = tmp
tmp = cur2.next
cur2.next = cur1
cur2 = tmp
cur1.next = cur2
if __name__ == '__main__':
i = 1
head = LNode()
tmp = None
cur = head
# 构造第一个列表
while i < 8:
tmp = LNode()
tmp.data = i
cur.next = tmp
cur = tmp
i += 1
print('排序前：')
cur = head.next
while cur is not None:
print(cur.data, end=' ')
cur = cur.next
Recorder(head)
print('\n排序后')
cur = head.next
while cur is not None:
print(cur.data, end=' ')
cur = cur.next
运行结果以下：
排序前：
1 2 3 4 5 6 7
排序后
1 7 2 6 3 5 4web