一个单向链表，奇数节点是升序、偶数节点是降序，怎么样将链表转变成降序的链表？｜阿里巴巴客户端面经解析

60 秒回答模板

先明确这里的奇数节点、偶数节点指的是链表中的位置编号，而不是节点值的奇偶。原链表按位置交错组成两条有序链：奇数位置节点形成一条升序链，偶数位置节点形成一条降序链。目标是把整体链表变成降序，所以不需要重新排序所有节点。做法是先遍历原链表，将奇数位置节点和偶数位置节点原地拆成两条链；然后将奇数位置的升序链反转，使它也变成降序；此时就得到两条降序链表，再用归并两个有序链表的方式，按较大值优先连接节点，得到最终降序链表。整个过程每个节点只访问常数次，时间复杂度是 O(n)，只修改 next 指针，不新建节点，额外空间复杂度是 O(1)。

考点 先澄清节点含义

主线 拆出两条子链

易错点 把奇数节点误解成节点值为奇数，导致错误地按值分类而不是…

深入解析

先澄清节点含义

题目里的奇数节点和偶数节点通常指链表位置的奇偶，例如第 1、3、5 个节点属于奇数位置链，第 2、4、6 个节点属于偶数位置链，而不是节点值本身是奇数还是偶数。这个澄清很重要，因为算法的可利用条件来自位置序列的有序性。如果误解成值的奇偶，就会走向按值分类，破坏题目给出的升序、降序结构。

拆出两条子链

原链表是单向链表，奇数位置和偶数位置节点交错出现。第一步可以用一个位置计数器遍历链表，把当前节点从原链表中摘下来，再接到 odd 链或 even 链的尾部。为了避免旧的 next 指针残留导致链表串联错误，每次摘下节点后最好先保存 next，再把当前节点的 next 置空，然后追加到对应链表。这样拆完后，odd 链保持原来的奇数位顺序，even 链保持原来的偶数位顺序。

利用已有有序性

拆完之后，奇数位置链按题意是升序，偶数位置链按题意是降序。目标是整体降序，所以偶数链已经符合目标方向，奇数链只差方向相反。此时不应该对所有节点做通用排序，因为那会把复杂度提高到 O(n log n)，也没有利用题目的特殊性质。更直接的做法是反转奇数链，升序链反转后自然变成降序链。

反转奇数链

反转单链表可以用三个指针完成：prev 表示已经反转好的头部，cur 表示当前处理节点，next 保存后续链表入口。每次把 cur.next 指向 prev，再整体向前推进。反转结束后，prev 就是新头节点。因为 odd 链原本是升序，比如 1 -> 3 -> 5，反转后变成 5 -> 3 -> 1，刚好变成降序，为后面的归并创造统一条件。

降序归并两条链

反转奇数链后，odd 和 even 都是降序链。最后一步就是合并两个降序有序链表，每次比较两个链表头节点的值，取较大的节点接到结果链后面。这里同样只需要改 next 指针，不需要创建新节点。若其中一条链先为空，剩余的另一条链本来就是降序，可以直接接到结果后面。最终得到的链表从头到尾满足降序。

复杂度与边界情况

整个流程包括拆链、反转、归并三段，每段都是线性处理，所以总时间复杂度是 O(n)。所有操作都在原节点上修改 next 指针，只使用若干辅助指针，因此额外空间复杂度是 O(1)。边界情况包括空链表、只有一个节点、只有两个节点、奇偶链长度不一致等。由于拆链和归并都按是否为空推进，这些情况可以自然覆盖。

javascript

拆链、反转、降序归并

function transform(head) {
  let oddDummy = new ListNode(0), evenDummy = new ListNode(0);
  let oddTail = oddDummy, evenTail = evenDummy;
  let cur = head, index = 1;
  while (cur) {
    const next = cur.next;
    cur.next = null;
    if (index % 2 === 1) {
      oddTail.next = cur;
      oddTail = cur;
    } else {
      evenTail.next = cur;
      evenTail = cur;
    }
    cur = next;
    index++;
  }

  const oddDesc = reverse(oddDummy.next);
  return mergeDesc(oddDesc, evenDummy.next);
}

function reverse(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

function mergeDesc(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val >= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
    tail.next = null;
  }
  tail.next = a || b;
  return dummy.next;
}

dummy 只用于简化指针拼接，核心节点仍然复用原链表节点。
如果不允许创建辅助节点，可以改用 head、tail 变量维护结果链。

易错点

把奇数节点误解成节点值为奇数，导致错误地按值分类而不是按位置拆链。
拆分链表时没有断开当前节点的 next，结果保留旧连接，可能造成链表串错或成环。
把偶数位降序链也反转了一次，导致它变成升序，后续无法直接做降序归并。
合并两条降序链时错误地选择较小节点，最终得到升序或局部乱序结果。
使用数组收集节点再排序，虽然能得到答案，但没有体现 O(1) 额外空间的链表解法。

面试官追问

如果链表长度为奇数或偶数，会影响算法吗？

不会影响。奇数位链和偶数位链的长度最多相差一个节点，拆链时按位置追加即可。后续反转 odd 链和归并两条降序链都只依赖链表是否为空，不依赖两条链长度相等。

为什么不能直接反转整个原链表？

直接反转整个原链表只会把原来的交错顺序倒过来，并不能保证整体降序。题目保证的是奇数位子序列升序、偶数位子序列降序，必须先把这两个子序列拆出来，才能利用它们的有序性。

如果要求升序结果，应该怎么改？

如果目标是升序，奇数位链已经是升序，可以保留；偶数位链是降序，需要先反转成升序。之后按照升序归并两个有序链表，每次选择较小的头节点即可。

能不能不使用哑节点 dummy？

可以不用，但代码会更容易出现头节点初始化分支。dummy 节点本身只是一个辅助指针容器，不代表创建业务节点；如果严格要求完全不新建节点，也可以用 head 和 tail 手动维护结果链。

如果存在相等元素，归并时怎么处理？

相等元素选择任意一边都能保持降序。为了行为稳定，可以约定当 odd.val >= even.val 时优先取 odd，或者优先取 even。这个选择不影响正确性，只影响相等节点的相对顺序。