【PAT】1028.List Sorting

**PAT1028.List Sorting**

在这个问题中，我们需要实现一个函数，能够对一个给定的链表进行排序。链表中的元素是按照某种顺序排列的，我们需要将这些元素重新排列成升序或降序。

### 链表结构定义首先，我们需要定义链表的结构：

cppstruct ListNode {
 int val;
 ListNode* next;
 ListNode(int x) : val(x), next(NULL) {}
};

这个结构中，`val`表示链表中的元素值，而`next`指向下一个链表节点。

### 排序函数实现现在，我们可以开始实现排序函数：

cppListNode* sortList(ListNode* head) {
 // 如果链表为空，则直接返回 if (!head || !head->next) return head;

 // 将链表分成两个部分：前半部分和后半部分 ListNode* mid = getMid(head);
 ListNode* midNext = mid->next;
 mid->next = NULL;

 // 递归地对前半部分和后半部分进行排序 ListNode* left = sortList(head);
 ListNode* right = sortList(midNext);

 // 将两个有序链表合并起来 return mergeTwoLists(left, right);
}

这个函数首先检查链表是否为空，如果是，则直接返回。然后，它将链表分成前半部分和后半部分，并递归地对每个部分进行排序。最后，它将两个有序链表合并起来。

### getMid函数实现`getMid`函数用于找到链表的中间节点：

cppListNode* getMid(ListNode* head) {
 // 如果链表只有一个元素，则返回该元素 if (!head || !head->next) return head;

 ListNode* slow = head;
 ListNode* fast = head;

 // 使用快慢指针找到链表的中间节点 while (fast->next && fast->next->next) {
 slow = slow->next;
 fast = fast->next->next;
 }

 return slow;
}

这个函数使用快慢指针的方式来找到链表的中间节点。

### mergeTwoLists函数实现`mergeTwoLists`函数用于合并两个有序链表：

cppListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 // 如果l1为空，则返回l2 if (!l1) return l2;

 // 如果l2为空，则返回l1 if (!l2) return l1;

 // 合并两个链表 if (l1->val < l2->val) {
 l1->next = mergeTwoLists(l1->next, l2);
 return l1;
 } else {
 l2->next = mergeTwoLists(l1, l2->next);
 return l2;
 }
}

这个函数首先检查两个链表是否为空，如果是，则直接返回一个空链表。然后，它合并两个有序链表。

### 总结在本文中，我们实现了一个对链表进行排序的函数。该函数首先将链表分成前半部分和后半部分，然后递归地对每个部分进行排序。最后，它将两个有序链表合并起来。这个函数使用快慢指针的方式来找到链表的中间节点，并使用递归的方式来实现链表的排序。

###代码示例

cppint main() {
 // 创建一个链表：1 ->2 ->3 ->4 ->5 ListNode* head = new ListNode(1);
 head->next = new ListNode(2);
 head->next->next = new ListNode(3);
 head->next->next->next = new ListNode(4);
 head->next->next->next->next = new ListNode(5);

 // 对链表进行排序 ListNode* sortedHead = sortList(head);

 // 打印排序后的链表 while (sortedHead) {
 std::cout << sortedHead->val << " ";
 sortedHead = sortedHead->next;
 }

 return0;
}

这个代码示例首先创建一个链表：1 ->2 ->3 ->4 ->5，然后对该链表进行排序。最后，它打印排序后的链表。

###代码注释

cpp// 对链表进行排序的函数ListNode* sortList(ListNode* head) {
 // 如果链表为空，则直接返回 if (!head || !head->next) return head;

 // 将链表分成前半部分和后半部分 ListNode* mid = getMid(head);
 ListNode* midNext = mid->next;
 mid->next = NULL;

 // 递归地对前半部分和后半部分进行排序 ListNode* left = sortList(head);
 ListNode* right = sortList(midNext);

 // 将两个有序链表合并起来 return mergeTwoLists(left, right);
}

// 获取链表的中间节点的函数ListNode* getMid(ListNode* head) {
 // 如果链表只有一个元素，则返回该元素 if (!head || !head->next) return head;

 ListNode* slow = head;
 ListNode* fast = head;

 // 使用快慢指针找到链表的中间节点 while (fast->next && fast->next->next) {
 slow = slow->next;
 fast = fast->next->next;
 }

 return slow;
}

// 合并两个有序链表的函数ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 // 如果l1为空，则返回l2 if (!l1) return l2;

 // 如果l2为空，则返回l1 if (!l2) return l1;

 // 合并两个链表 if (l1->val < l2->val) {
 l1->next = mergeTwoLists(l1->next, l2);
 return l1;
 } else {
 l2->next = mergeTwoLists(l1, l2->next);
 return l2;
 }
}

这个代码注释首先对链表进行排序，然后获取链表的中间节点，并合并两个有序链表。