怎么对链表进行排序代码
时间: 2023-05-23 11:07:19 浏览: 68
A:
可以使用常见的排序算法来对链表进行排序,比如冒泡排序、插入排序、归并排序和快排等。以下是使用归并排序对链表进行排序的示例代码:
```python
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 使用归并排序对链表进行排序
def sortList(head: ListNode) -> ListNode:
if not head or not head.next:
return head
pre, slow, fast = None, head, head
while fast and fast.next:
pre, slow, fast = slow, slow.next, fast.next.next
pre.next = None # 断开链表
left, right = sortList(head), sortList(slow)
dummy = ListNode(-1)
cur = dummy
while left and right:
if left.val < right.val:
cur.next, left = left, left.next
else:
cur.next, right = right, right.next
cur = cur.next
cur.next = left if left else right
return dummy.next
```
说明:将链表分为两个子链表,分别排序后再将两个有序子链表合并起来。
时间复杂度:O(nlogn),空间复杂度:O(logn)。