题目

给定链表L0_L1_L2_..._Ln，将链表重新排序为L0_Ln_L1_Ln-1_L2_Ln-2_L3...,要求：（1）在原来链表上进行排序，不能申请新的结点；（2）只能修改结点的next域，不能修改数据域；

思路

用快慢指针找出中间结点，之后用前面写的逆序函数得到Ln_Ln-1_Ln-2-...
再依次连接各结点。

class LHead:
    def __init__(self):
        self.next = None
    
    def get_ordered_list(self): # 以列表形式打印顺序表
        order_list = []
        if self.next == None or self == None:
            return order_list
        else:
            cur = self.next
            while cur != None:
                order_list.append(cur.data)
                cur = cur.next
            return order_list
        
    def ordered_list_size(self): #获得链表长度
        
        return len(self.get_ordered_list())
    
    def create_ordered_list(self,size): #在新建头结点后面生成有序链表
        i = 0
        tmp = None
        cur = self
        ordered_list = []
         #构造单链表
        while i < size:
             tmp = LNode(i)
             tmp.next = None
             cur.next = tmp
             cur = tmp
             i += 1
        cur = self.next
        while cur != None:
            ordered_list.append(cur.data)
            cur = cur.next
        return ordered_list,self
    
#%%
class LNode:
    def __init__(self,data):
        self.data = data
        self.next = None


#%%
# 就地逆序
def reverse_list(head):
    if head == None or head.next == None:
        return None
    else:
        cur = head.next
        pre = head
        inext = cur.next
        cur.next = None
        pre = cur
        cur = inext
        while cur.next != None:
            inext = cur.next
            cur.next = pre
            pre = cur
#            cur = cur.next
            cur = inext
            
        cur.next = pre
        head.next = cur
    return head
            
#%%
def resort_list(head):
    if head == None or head.next == None or head.next.next == None:
        return head
    elif head.next.next.next == None:
        pre = head.next
        cur = pre.next
        head.next = cur
        cur.next = pre
        pre.next = None
        return head
    else:
        slow = head
        fast = head
        while fast != None:
            slow = slow.next
            if fast.next == None:
                break
            fast = fast.next.next
        new_list = slow.next
        slow.next = None
        new_head = LHead()
        new_head.next = new_list
        new_head = reverse_list(new_head)
        
        cur1 = head.next
        cur2 = new_head.next
        while cur2 != None:
            inext1 = cur1.next
            if cur2.next == None:
                end2 = cur2
            inext2 = cur2.next
            cur1.next = cur2
            cur2.next = inext1
            
            cur1 = inext1
            cur2 = inext2
        if cur1:
            end2.next = cur1
        return head