Bytedance a force link without high frequency interview questions – sort odd rise even fall linked list

preface

This article is about frequent interview questions that you can’t find on Leetcode. Let’s take a look at some of the original statements of the noodle Sutra.

• In a linked list, odd numbers grow in order and even numbers decrease in order. How can we make the list grow from small to large? (2021.3 Bytedance – Tiktok – Data Research and Development)
• Given a linked list, the odd bits of the list are sorted in ascending order and the even bits in ascending order (2021.01 bytedance – education – back end)
• 1->4->3->2->5 Given a list with odd parts increasing and even parts decreasing, it is required to change the list to increasing within O(n) time complexity, about 5 minutes (2020.07 bytes beat – Test development)
• A list with odd digits ascending and even digits descending requires ordering O(1) in space O(n) of time? (2020.07 Bytedance – backend)

It can be seen that bytedance is easy to investigate this problem, we must pay attention to!!

Topic describes

Given a linked list with odd digits ascending and even digits descending, reorder it.

Input: 1 – > 6-8 – > 3 – > > 5 – > 4 – > 7 – > 2 – > NULL output: 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL

Subject analysis

According to the odd and even position resolution list, 1 – > 3 – > 5-7 – > > NULL and 8 – > 6 – > 4 – > 2 – > NULL inversion accidentally linked list, 1 – > 3 – > 5-7 – > > NULL and 4 – > 2 – > 6-8 – > > NULL merge two order list, 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL time complexity is O (N), space complexity O (1).

The idea is very clear, but it’s actually a little difficult to implement, because each step here can actually be isolated as a problem. Steps 2 and 3 correspond to force links 206. Reverse lists and 21. Merge two ordered lists, while the solution of step 1 corresponds to the solution of step 328. Odd-even lists are pretty much the same. If you understand the three lines of Leetcode, you will be able to solve the problem in this article.

Reference code

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        
Copy the code