【Day5】力扣第328题，奇偶链表

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

前言
大家好我是良辰丫🚀🚀🚀今天带大家刷一个力扣链表题有人可能会说一道题够嘛刚开始刷题别着急毕竟心急吃不了热豆腐🍾🍾🍾我们慢慢来先积累思想脑子里的东西多了敲代码敲得多了有一天你会发现你也可以做到“下笔如有神”废话不多说我们来看一下这道题我把题目链接放到了下边大家可以去做一下。💖💖💖
题目链接 力扣第328题奇偶链表

🧑个人主页良辰针不戳
📖所属专栏EveryDay学java
🍎励志语句生活也许会让我们遍体鳞伤但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连关注点赞收藏。
📜作者能力有限也会出错希望大家可以指正。
💞愿与君为伴共探Java汪洋大海。

1、题目介绍

题目:

给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。
第一个节点的索引被认为是奇数第二个节点的索引为偶数以此类推。
请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

在这里插入图片描述

输入: 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]

提示

n == 链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106

2、题目分析

做题的第一步是什么呢有人说思路分析你连题目都没看懂笔试的时候做编程题题目都没读懂或者懵懵懂懂的读错了题分析了半天写了不着边际的代码时间浪费了那么多从头再来时间不等人呀就因为不细心本来可以做出来的题目没有做出来这家公司与你无缘了,哈哈还是注重细节。

我做这道题就看错了人家写的是奇数的节点和偶数节点而我看成了数值val为奇数和偶数一顿操作猛如虎结果答案不对脑瓜里充满了问号捉摸了半天代码没毛病呀然后答案进行对比才发现了错误因此呢大家一定要看清题而且把题目的例子多看几遍这样有助于消化题目。

题目分析

奇数节点放左边偶数节点放右边遇到这种分段题咱们首先要培养的就是分段思路分成两个节点段奇数段和偶数段通过遍历找到奇数节点和偶数节点进行拼接。
那么如何进行拼接呢我们要有双指针思想前段和后段分别有首尾指针。下面我将通过注释的方式详细解析代码希望能给大家带来帮助。

class Solution {
    public ListNode oddEvenList(ListNode head) {
    //没有节点或者只有一个节点直接返回头结点
    //0个或1个就没有操作的必要了
        if(head == null || head.next == null){
            return head;
        }
        //s:start
        //e:end
        //bs:前段首指针
        //be:前段尾指针
        //as:后段首指针
        //ae:后段尾指针
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        //通过cur进行遍历
        ListNode cur = head;
        //通过计数器记录第几个节点
        int count = 1;
        while(cur != null){
        //奇数节点放在前一段
            if(count % 2 == 1){
            //前段节点第一次插入时首尾指针都需要移动
                if(bs == null){
                    bs = cur;
                    be = cur;
             //不是第一次插入时只需要移动尾节点
                } else {
                    be.next = cur;
                    be = be.next;
                }
          //偶数节点放在后一段
            } else {
            //后段当节点第一次插入时首尾指针都需要移动
                if(as == null){
                    as = cur;
                    ae = cur;
             //后段当节点不是第一次插入时只需要移动尾节点
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            //cur的移动放在外面减少时间复杂度
            cur = cur.next;
            //计数器加加
            count++;
        }
        //遍历完成后进行拼接操作
        //前一段无数据时直接返回后一段
        if(bs == null){
            return as;
        }
        //走到这一步说明前一段有数据前后进行拼接
        be.next = as;
        //后一段有数据时后一段尾巴一定要有null要不然打印无法停下来
        if(as != null){
            ae.next = null;
        }
        //拼接完成后返回第一段首节点
        return bs;
    }
}