讨论/技术交流/交流|字节跳动一道力扣没有的高频题——排序奇升偶降链表/
交流|字节跳动一道力扣没有的高频题——排序奇升偶降链表

前言

本系列文章是补充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. 按奇偶位置拆分链表,得1->3->5->7->NULL和8->6->4->2->NULL
  2. 反转偶链表,得1->3->5->7->NULL和2->4->6->8->NULL
  3. 合并两个有序链表,得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        
        return dumpy.next    
    def merge(self,p,q):        
        head = ListNode(-1)        
        r = head        
        while p and q:            
            if p.val <= q.val:               
                r.next = p                
                p = p.next            
            else:                
                r.next = q                
                q = q.next            
            r = r.next        
        if p:            
            r.next = p        
        if q:            
            r.next = q        
        return head.next

13
共 2 个回复

更新了一道腾讯PCG、TEG都考过的一道题 https://leetcode-cn.com/circle/discuss/l8fl8B/

大哥
关注你了
有没有tencent的高频题整点
gkd