LeetCode – 328 – 奇偶链表 – java – 一种思维,两种解法

云惠网小编 2021年12月29日19:19:42
评论
2316字阅读7分43秒
摘要

文章目录题目解题思维1:代码附图解题思维二来看,我们创建两个 节点 引用 odd(奇数)等于 head(第一个节点的地址),第二个节点 为 even(偶数)。因为我们是直接在原链表上开刀,所以 odd不用在创建一个替身去链接后面的节点(原链表有head,而odd==head,让 odd名副其实的去链接后面的节点),但是 even 原链表中可没有具体的引用记住它的地址,所以我们需要为 even 创建一个替身去链接节点。现在我们的前期准备已完成,现在我们要思考一个问题,原链表的头节点为奇数,头节点(head.n

广告也精彩


/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return null;
}
ListNode evenLinked = new ListNode();// 偶数链表头节点
ListNode evenCur = evenLinked;// 偶数链表头节点的替身
ListNode oddLinked = new ListNode();// 奇数链表头节点
ListNode oddCur = oddLinked;// 奇数链表头节点替身
int n  = 1;// 用来表示 现在 head 指向的是第几个节点,方便我们来判断个数的奇偶性
while(head!=null){
if(n % 2 != 1){//判断 第 n 个节点, n 是否偶数,是就接入偶数链表
evenCur.next = head;
evenCur = evenCur.next;
}else{//  第 n 个节点, n 既然不是偶数,那就是奇数了,就接入奇数链表
oddCur.next = head;
oddCur = oddCur.next;
}
head = head.next;// head 继续遍历原链表 
n++;// 此时 head 指向了 第 n +1 个节点 
}
//因为偶数位置的节点放在右边的,所以需要注意偶数链表最后一个节点的next,需要置为null。防止造成环!
evenCur.next = null;
oddCur.next = evenLinked.next;// 将奇数链表 和 偶数链表结合,其结果就是我们想要的
return oddLinked.next;// 在合并后,奇数链表的节点是前面的,所以我们返回 奇数链表的头节点的next。
// 因为我们奇数链表是一个带头的链表,所有头节点的值是不重要的!
}
}
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return null;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenCur = even;
while(evenCur != null && evenCur.next != null){
odd.next = evenCur.next;
odd = odd.next;
evenCur.next = odd.next;
evenCur = evenCur.next;
}
odd.next = even;
return head;
}
}

代码如下



在这里插入图片描述

在这里插入图片描述

文章目录

  • 题目
  • 解题思维1:
    • 代码
    • 附图
  • 解题思维二
    • 来看,我们创建两个 节点 引用 odd(奇数)等于 head(第一个节点的地址),第二个节点 为 even(偶数)。
    • 因为我们是直接在原链表上开刀,所以 odd不用在创建一个替身去链接后面的节点(原链表有head,而odd==head,让 odd名副其实的去链接后面的节点),但是 even 原链表中可没有具体的引用记住它的地址,所以我们需要为 even 创建一个替身去链接节点。
    • 现在我们的前期准备已完成,现在我们要思考一个问题,原链表的头节点为奇数,头节点(head.next)的下一个节点为偶数(even),那么 偶数节点下一个节点就是奇数节点(evenCur.next),我们就将其接入 奇数节点的后面(odd.next),然后,该节点下一个节点不就偶数节点了!我们再将其接入 偶数节点的后面(even.next)。
    • 最后只需要拼接就行了
    • 代码如下

来看,我们创建两个 节点 引用 odd(奇数)等于 head(第一个节点的地址),第二个节点 为 even(偶数)。

现在我们的前期准备已完成,现在我们要思考一个问题,原链表的头节点为奇数,头节点(head.next)的下一个节点为偶数(even),那么 偶数节点下一个节点就是奇数节点(evenCur.next),我们就将其接入 奇数节点的后面(odd.next),然后,该节点下一个节点不就偶数节点了!我们再将其接入 偶数节点的后面(even.next)。


在这里插入图片描述

题目

在这里插入图片描述

在这里插入图片描述

解题思维1:

解题思维二

代码


附图

在这里插入图片描述

与上题相同的是我们还是用了将链表分割成两部分,最后合并。
不同的是,我们是直接在原链表身上直接开刀。
首先我们知道 这题的奇偶性是以 第 n 个节点,n 的奇偶性决定的。
要求 第 n 节点的 n 为奇数的放在链表左边,为偶数统一放在链表的右边。

创建里两个头节点,分别代表 奇数(odd)链表的头节点, 偶数(even)链表的头节点。
再分别 这两个节点创建一个替身,用来连接 对应各自属性的节点。
至于题目的 head,就不用创建替身,直接用head 去遍历链表就行了。
需要注意的是 链表是没有下标这个东西的,所以我们需要定义整形变量 n 等于1,因为题目说链表的第一个节点为奇数,第二个节点为偶数。
最后将 偶数链表 和 奇数链表 拼接起来就可以了。


最后只需要拼接就行了

在这里插入图片描述

因为我们是直接在原链表上开刀,所以 odd不用在创建一个替身去链接后面的节点(原链表有head,而odd==head,让 odd名副其实的去链接后面的节点),但是 even 原链表中可没有具体的引用记住它的地址,所以我们需要为 even 创建一个替身去链接节点。

在这里插入图片描述



本文转自 https://blog.csdn.net/DarkAndGrey/article/details/122199667

腾讯云618
未分类
云惠网小编
SpringCloud -- Config、Bus解析

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
[深度解剖C语言] --关键字 static

[深度解剖C语言] –关键字 static

static ---最名不副实的关键字目录1.static修饰全局变量2.static修饰函数3.static修饰局部变量static的作用:1.static修饰全局变量我们创建两...
Java数据结构-认识顺序表

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论