前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode.328奇偶链表——Javascript实现方案

leetcode.328奇偶链表——Javascript实现方案

作者头像
虎妞先生
发布2022-10-27 19:47:13
2740
发布2022-10-27 19:47:13
举报

持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第2天,点击查看活动详情

前言

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

image.png
image.png

奇偶链表

描述

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

示例

代码语言:javascript
复制
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
代码语言:javascript
复制
输入: 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)

代码

代码语言:javascript
复制
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指向偶数链表的开头

原题链接

https://leetcode.cn/problems/odd-even-linked-list/

最后,这是我第一次参加更文活动,茫茫人海中,如果有幸遇到你,读到我这篇文章,那真是太好了。我深知还有很多不足,希望大家能多提建议,还是想舔着脸皮,向屏幕前的大帅比们,大漂亮们,恳请一个小小的点赞,这会是对我莫大鼓励。也祝愿点赞的大帅比们,大漂亮们升职加薪走向人生巅峰!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 奇偶链表
    • 描述
      • 示例
        • 解析
          • 代码
            • 一句话总结
              • 原题链接
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档