从键盘上输入n(>6)个随机整数构成单链 表，在不申请新的节点空间的情况下对 链表进行排序操作，使其节点按照非递 减顺序依次排列。 Ø要求：1、创建链表； 2、原地排序。

这种问题通常涉及链表的操作以及原地排序算法，如归并排序或者快速排序的部分思路。我们可以使用两个指针，一个慢指针每次移动一步，一个快指针每次移动两步，找到当前未排序部分的最大值和次大值，然后将这两个元素插入到已排序链表的适当位置。以下是步骤概述：

1. **创建链表**：首先，我们需要创建一个头结点，并通过循环获取用户输入的n个随机整数作为节点值，每个新节点链接到前一个节点的下一个节点。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def create_linked_list(n):
    head = ListNode()
    current = head
    for _ in range(n):
        val = int(input("请输入一个整数："))
        current.next = ListNode(val)
        current = current.next
    return head

2. **原地排序**：接着，我们采用类似于希尔排序的方式遍历链表，使用插入排序的思想，不断缩小间隔，直到间隔为1，然后插入相邻元素使其有序。

def sort_linked_list(head):
    if not head or not head.next:
        return head
    
    # 使用快慢指针找到中间节点
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    
    # 分治处理未排序部分
    mid = slow.next
    slow.next = None
    sort_linked_list_by_insertion_sort(mid)

    # 将有序链表合并回原始链表
    prev, curr = None, head
    while curr:
        if curr.val <= mid.val:
            if prev:
                prev.next = curr
            else:
                head = curr
            prev = curr
        curr = curr.next
        if curr == mid:
            prev.next = mid
            break
    prev.next = mid.next
    return head

# 原地插入排序函数
def sort_linked_list_by_insertion_sort(curr):
    while curr and curr.next:
        smaller = curr.next
        while smaller and smaller.val < curr.val:
            smaller = smaller.next
        if smaller is not None:
            curr.next = smaller.next
            smaller.next = curr
        else:
            curr.next = None
        curr = curr.next