LeetCode 328. Odd Even Linked Li

问题描述

给定一个单链表，将所有偶数节点跟在奇数节点后。注意这里的奇偶指的是节点序号，而不是节点值。

请尝试就地完成，且空间复杂度为 O(1) ，时间复杂度为 O(nodes) 。

栗 1：

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

栗 2：

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

注意：

• 奇数和偶数组中的节点顺序应该和原有顺序保持一致。
• 第一个节点为奇数，第二个节点为偶数，依次类推。
• 链表长度范围在 [0, 10^4] 之间。

想看英文原文的戳这里。

解题思路

这题最需要注意的一点是：将偶数序号的节点放在奇数序号的节点之后。而不是节点的值，这点刚开始我理解错了，疑惑了好久。

假设原链表如下：

image.png

经过处理后，结果应该是：2->1->3->4。

解法 1

既然要保持节点原有的顺序，那么我们可以逐个遍历节点进行处理。当遇到奇数号节点时（假设序号为 m），将其串到奇数号 m - 2 节点后，同时其前的偶数号 m - 1 与后面的偶数号 m + 1 建立连接，最后奇数号节点 m 与偶数号 m - 1 建立连接。

文字描述有点绕，不太好理解，请看下图：

image.png

这里的操作分为 3 步：

1. 奇数 1 号与奇数 3 号相连：将 1 号节点（节点值为 3）与 3 号节点（节点值为1）建立连接。2->1。
2. 偶数 2 号与偶数 4 号相连：将 2 号节点（节点值为 3）与 4 号节点（节点值为 4）建立连接。3->4。
3. 奇数 3 号与偶数 2 号相连：将 3 号节点（节点值为 1）与 2 号节点（节点值为 3）建立连接。1->3。

js 代码如下：

var oddEvenList = function (head) {
  if (head) {
    // 指向奇数节点
    let p = head;

    // 当前节点
    let cur = head;

    // 前一节点
    let pre = null;

    // 记录第几个节点
    let i = 1;

    while (cur) {
      if (i % 2 === 1) {
        // 非第一个奇数节点
        if (pre) {
          const next = cur.next;

          // 插入到奇数节点后
          cur.next = p.next;
          p.next = cur;

          // 删除 cur
          pre.next = next;

          // 更新当前节点
          cur = next;

          // 指向插入的节点
          p = p.next;
        } else {
          pre = cur;
          cur = cur.next;
        }
      } else {
        pre = cur;
        cur = cur.next;
      }

      i += 1;
    }
  }
  return head;
};

解法 2

同解法 1 的思路大致相同，只不过在第 3 步时，是在处理完所有节点后，最后建立奇数节点与偶数节点的连接。

处理步骤如下图：

image.png

步骤描述如下：

1. 将奇数号节点形成一条链，最后一个节点为 odd。
2. 将偶数号节点形成一条链，头结点为 evenHead。
3. 将最后的奇数号节点 odd 与偶数号头节点 evenHead 建立连接。

js 代码如下：

var oddEvenList = function (head) {
  if (head) {
    // 奇数号链最后一个节点
    let odd = head

    // 偶数号链头
    let evenHead = head.next

    // 偶数号链最后一个节点
    let even = evenHead

    while (even) {
      // 奇数号进行链接
      odd.next = even.next

      // 记录最后一个奇数号节点
      if (odd.next) {
        odd = odd.next
      }

      // 偶数号进行链接
      even.next = odd.next
      even = even.next
    }

    // 奇数号节点与偶数号节点建立连接
    odd.next = evenHead
  }

  return head
}