前言

今天刷了几道链表的经典问题，难度有简单的，也有中等，特意在此记录一下，和大家分享解题过程和思路

奇偶链表

描述

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

示例

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

解析

• 题目中已经说明是要区分奇数和偶数的节点，一般都这么说的题目，都会用到双指针来处理。如果是数组，我们很好处理，但是如果是链表，指针只能向前，不能向后，这一点需要特别注意。
  
• 奇偶指针循环链表，奇数指针不断串连奇数节点，偶数指针不断串连偶数节点，最后奇数指针的结尾连接偶数节点的开始
  
• 首先判断如果输入为空，那么直接返回null
  
• 定义两个指针，odd 指向奇数位，even 指向偶数位
  
• 奇数位next指向，偶数位的next.(偶数位的下一位肯定是奇数位)
  
• 同理，偶数位next指向，奇数位的next.(奇数位的下一位肯定是偶数位)
  
• 当偶数指针为空时，循环结束。
  
• 最后奇数位的next 指向偶数位的链表
  
• 时间复杂度在O（n）
  
• 空间复杂杜在O（1）

代码

var oddEvenList = function(head) {
    if (head === null) {
        return head;
    } // 如果输入为空，那么直接返回null
    let evenHead = head.next;
    let odd = head, even = evenHead;
    while (even !== null && even.next !== null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;

一句话总结

奇偶两个指针 指针每次都间隔一个跳跃 循环结束把奇数链表next指向偶数链表的开头

原题链接

leetcode.cn/problems/od…