重排链表问题

**重排链表问题**

在数据结构中，链表是一种常见的线性数据结构。链表中的每个结点都包含一个值和一个指向下一个结点的引用。在某些情况下，我们需要对链表进行重排，以满足特定的需求。

**问题描述**

假设我们有一个链表，链表中每个结点都包含一个整数值。我们的任务是将链表中的所有结点按照一定的顺序重新排列，使得链表中的每个结点的值都大于其前驱结点的值。

**解决方案**

为了解决这个问题，我们可以使用以下方法：

1. **首先，遍历链表，将每个结点的值存储在一个数组中。**
2. **然后，对数组进行排序，以确保每个元素都大于其前驱元素。**
3. **最后，将排序后的数组重新排列到链表中。**

**代码示例**

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef sortList(head):
 # 将链表中的所有结点的值存储在一个列表中 values = []
 current = head while current:
 values.append(current.val)
 current = current.next # 对列表进行排序 values.sort()
 # 将排序后的列表重新排列到链表中 dummy = ListNode(0)
 current = dummy for value in values:
 current.next = ListNode(value)
 current = current.next return dummy.next# 测试代码head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

sorted_head = sortList(head)
while sorted_head:
 print(sorted_head.val, end=" ")
 sorted_head = sorted_head.next