题解 | #排序奇升偶降链表#

排序奇升偶降链表

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 
                
        
            
        

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
07-09 15:55
门头沟学院 Java
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务