1. 题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

  1. 输入: 1->2->3->4->5->NULL
  2. 输出: 1->3->5->2->4->NULL

示例 2:

  1. 输入: 2->1->3->5->6->4->7->NULL 
  2. 输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。

  • 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

    2. 解题思路

    这道题的思路就是遍历链表，将链表的中的所有的元素分为a和b两个链表，分别用来保存奇数值和偶数值，遍历结束之后，偶数链表拼接在奇数链表后面。具体实现过程如下：

  • 首先将链表节点数为0，1，2的情况排除掉，直接返回head

  • 定义a和b两个链表，分别表示奇数和偶数节点，用node来暂时保存b链表的头结点，便于后面拼接
  • 使用while循环对a和b链表进行交叉遍历赋值。a和b一直指向奇数链和偶数链的最后一个节点
  • 将两个链表进行拼接，并返回

    3. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val, next) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.next = (next===undefined ? null : next)
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @return {ListNode}
    11. */
    12. var oddEvenList = function(head) {
    13.   if(head === null || head.next === null || head.next.next === null){
    14.       return head
    15.   }
    16.   let a = head       // 存放奇数节点
    17.   let b = head.next  // 存放偶数节点
    18.   const node = head.next   // 记录b链表的头节点
    19.   while(b !== null && b.next !== null){
    20.       a.next = b.next
    21.       a = a.next
    22.       b.next = a.next
    23.       b = b.next
    24.   }
    25.   a.next = node
    26.   return head
    27. };

    4. 提交结果

    328. 奇偶链表 - 图1