Leetcode奇偶链表

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

例1：

例2：

二、解题思路

在寻找这道题的思路上，倒并没有阻滞。主要是几个关键点，维护两个指针p1、p2，p1指向奇数节点，p2指向偶数节点。以例1为例，在更新过程中，每次首先找到后续节点，当p1、p2分别指向1、2时，找到后续节点3、4，然后将3挂到1节点后，4挂到2节点后，最后将p1指向3节点，将p2指向4节点。每次更新过程都是这样的寻找+挂载+移动。因为最后需要把奇偶链表链接起来，所以需要在一开始保存头节点h1、h2分别指向链表第一个和第二个节点，在指针移动结束后，将h2挂载到最后的p1，并返回h1。

当然，有一些细节需要注意，例如遍历到最后出现p2后续节点为空或者p1、p2后续节点均为空这两种情况怎么处理；节点数量为0和1时作为特殊情况要首先处理。

三、AC代码

var oddEvenList = function(head) {
    if(!head?.next) return head
    let h1 = p1 = head;
    let h2 = p2 = head.next;
    while(p1&&p2){
        p1.next = p2.next;
        if(p1.next) p1 = p1.next;
        if(p1){
            p2.next = p1.next;
            p2 = p2.next;
        }
    }
    p1.next = h2;
    return h1
    
};
复制代码

四、总结

虽然思路没有问题，但是在边界情况和具体指针移动的细节上还是经过调试和借鉴别人的答案才达到了最满意的解。