关于字节跳动:字节跳动一道力扣没有的高频面试题题排序奇升偶降链表

前言

本文章是讲 Leetcode 上找不到的面试高频题。
来看一下几篇面经的原文叙述。

• 链表，奇数地位按序增长，偶数地位按序递加，如何能实现链表从小到大？（2021.3 字节跳动 - 抖音 - 数据研发）
• 给定一个链表，此链表奇数位为升序排列，偶数位为降序排列（2021.01 字节跳动 - 教育 - 后端）
• 1->4->3->2->5 给定一个链表奇数局部递增，偶数局部递加，要求在 O(n) 工夫复杂度内将链表变成递增，5 分钟左右（2020.07 字节跳动 - 测试开发）
• 奇数位升序偶数位降序的链表要求工夫 O(n) 空间 O(1) 的排序？(2020.07 字节跳动 - 后端)

可见，字节跳动很容易考查过这道题，大家肯定要留神！！

题目形容

给定一个奇数位升序，偶数位降序的链表，将其从新排序。

输出: 1->8->3->6->5->4->7->2->NULL
输入: 1->2->3->4->5->6->7->8->NULL

题目剖析

按奇偶地位拆分链表，得 1 ->3->5->7->NULL 和 8 ->6->4->2->NULL
反转偶链表，得 1 ->3->5->7->NULL 和 2 ->4->6->8->NULL
合并两个有序链表，得 1 ->2->3->4->5->6->7->8->NULL
工夫复杂度为 O(N)，空间复杂度 O(1)。

思路很清晰，实现起来其实还是有些难度的，因为这里的每一步其实都能够独自抽出来作为一道题。
第 2 步和第 3 步别离对应的力扣 206. 反转链表和 21. 合并两个有序链表，而第 1 步的解法与 328. 奇偶链表差不多。
如果搞懂这 3 道 leetcode，那么本篇文章的这道题必定不在话下了。

参考代码

class ListNode:    
    def __init__(self, x):        
        self.val = x        
        self.next = None

class Solution:    
    def sortOddEvenList(self,head):     
        if not head or not head.next:      
            return head        
        oddList,evenList = self.partition(head)        
        evenList = self.reverse(evenList)        
        return self.merge(oddList,evenList)    

    def partition(self, head: ListNode) -> ListNode:        
        evenHead = head.next        
        odd, even = head, evenHead        
        while even and even.next:            
            odd.next = even.next            
            odd = odd.next            
            even.next = odd.next            
            even = even.next        
        odd.next = None        
        return [head,evenHead]    
    def reverse(self,head):        
        dumpy = ListNode(-1)        
        p = head        
        while p:            
            temp = p.next            
            p.next = dumpy.next            
            dumpy.next = p            
            p = temp