前言

本文章是讲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 = Noneclass 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