LeetCode 328. Odd Even Linked List

关注

发布于: 2020 年 08 月 04 日

问题描述﻿
给定一个单链表，将所有偶数节点跟在奇数节点后。注意这里的奇偶指的是节点序号，而不是节点值。
﻿
请尝试就地完成，且空间复杂度为  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] 之间。
﻿
想看英文原文的戳这里。
﻿
解题思路﻿
这题最需要注意的一点是：将偶数序号的节点放在奇数序号的节点之后。而不是节点的值，这点刚开始我理解错了，疑惑了好久。
﻿
假设原链表如下：
﻿
﻿
经过处理后，结果应该是：2->1->3->4。
﻿
解法 1﻿
既然要保持节点原有的顺序，那么我们可以逐个遍历节点进行处理。当遇到奇数号节点时（假设序号为 m），将其串到奇数号 m - 2 节点后，同时其前的偶数号 m - 1 与后面的偶数号 m + 1 建立连接，最后奇数号节点 m 与偶数号 m - 1 建立连接。
﻿
文字描述有点绕，不太好理解，请看下图：
﻿
﻿
这里的操作分为 3 步：
奇数 1 号与奇数 3 号相连：将 1 号节点（节点值为 3）与 3 号节点（节点值为1）建立连接。2->1。
偶数 2 号与偶数 4 号相连：将 2 号节点（节点值为 3）与 4 号节点（节点值为 4）建立连接。3->4。
奇数 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 步时，是在处理完所有节点后，最后建立奇数节点与偶数节点的连接。
﻿
处理步骤如下图：
﻿
﻿
步骤描述如下：
将奇数号节点形成一条链，最后一个节点为 odd。
将偶数号节点形成一条链，头结点为 evenHead。
将最后的奇数号节点 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
}
﻿