题解 | #排序奇升偶降链表#
排序奇升偶降链表
https://www.nowcoder.com/practice/3a188e9c06ce4844b031713b82784a2a
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # 学习中…… class Solution: def reversenode(self, root): pre = None while root: temp = root.next root.next = pre pre = root root = temp return pre def sortLinkedList(self , head: ListNode) -> ListNode: # 奇偶取出，偶反转 if not head or not head.next: return head odd = head even = head.next even_head = even while even and even.next: odd.next = even.next odd = odd.next even.next = odd.next even = even.next odd.next = None # 截断 # 如果even为None 说明是奇数列odd是最后一位，如果even.next为空说明是偶数 # 此时head已经发生变化 head是奇数列头节点 head.next 是奇数位了 newhead = self.reversenode(even_head) # 反转偶数链表 dummy = ListNode(0) cur = dummy while head and newhead: if head.val <= newhead.val: cur.next = head head = head.next else: cur.next = newhead newhead = newhead.next cur = cur.next cur.next = head if head else newhead # 最后如果奇数还有数连接到末尾否则是偶数 return dummy.next
查看17道真题和解析