LeetCode – 92 – 反转链表|| – java – 两种解法 – 细喔~

云惠网小编 2021年12月26日17:18:46
评论
2850字阅读9分30秒
摘要

文章目录题目解法一跟着我一步步来第一步: new 一个傀儡头节点 newHead,且 newHead.next == head。(这样做,我们就获得了 head 的 前驱节点。防止头节点head也是反转对象。)第二步:在创建一个 节点引用 prev,用来记录 left的前驱节点(通过for循环,让prev指向 left的前驱节点)第三步:寻找 right 位置的节点第四步:记录 rightNode 的 下一个节点的位置(rightNode.next),并将 prev.next(left位置的节点),rig

广告也精彩

第六步: 将 left 和 right 置回 初始位子(left <= right ),并接回链表。最终返回逆序完成之后的原链表。

解法二:

可以参考 这题LeetCode - 25. K 个一组翻转链表,因为我们第一种解放就与这题相同。


第四步:记录 rightNode 的 下一个节点的位置(rightNode.next),并将 prev.next(left位置的节点),rightNode 进行传参 给 反转方法myRreverse。

在这里插入图片描述

/**
* 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 reverseBetween(ListNode head, int left, int right) {
if(head == null || right == left){
return head;// 头节点为null,链表为空,反转链表没有意义(没有节点给你反转)
// right == left ,反转一个节点,等于没反转。也没有反转的意义
// 直接返回 head
}
ListNode newHead = new ListNode(0,head);
ListNode prev = newHead;
for(int i = 0; i < left - 1; i++){
prev = prev.next;
if(prev == null){// 防止空指针异常,另外防止 left 位置不合法(链表节点没有那么多)
return head;
}
}
ListNode cur = prev.next;
ListNode next = null;
for(int i = 0;i < right -left;i++){
next = cur.next;
cur.next = next.next;
next.next = prev.next;
prev.next = next;
}
return newHead.next;
}
}

题目

在这里插入图片描述

前面 跟解法一差不多(求 left位置的节点)。
在这里插入图片描述





解法一


在这里插入图片描述

第二步:在创建一个 节点引用 prev,用来记录 left的前驱节点(通过for循环,让prev指向 left的前驱节点)

&ensp;

跟着我一步步来

在这里插入图片描述


代码

在这里插入图片描述


附上程序

在这里插入图片描述

第一步: new 一个傀儡头节点 newHead,且 newHead.next == head。(这样做,我们就获得了 head 的 前驱节点。防止头节点head也是反转对象。)

在这里插入图片描述

在这里插入图片描述


在这里插入图片描述

文章目录

  • 题目
  • 解法一
    • 跟着我一步步来
      • 第一步: new 一个傀儡头节点 newHead,且 newHead.next == head。(这样做,我们就获得了 head 的 前驱节点。防止头节点head也是反转对象。)
      • 第二步:在创建一个 节点引用 prev,用来记录 left的前驱节点(通过for循环,让prev指向 left的前驱节点)
      • 第三步:寻找 right 位置的节点
      • 第四步:记录 rightNode 的 下一个节点的位置(rightNode.next),并将 prev.next(left位置的节点),rightNode 进行传参 给 反转方法myRreverse。
      • 第五步: 敲写 myReverse 方法,(跟这题 [LeetCode - 25. K 个一组翻转链表](https://blog.csdn.net/DarkAndGrey/article/details/122068701?spm=1001.2014.3001.5501) 一模一样)
      • 第六步: 将 left 和 right 置回 初始位子(left <= right ),并接回链表。最终返回逆序完成之后的原链表。
    • 附上程序
  • 解法二:
    • 代码

找到 链表 left ~ right 这个范围,将它“截取出来”,单独进行反转,反转完后,将之接回链表中,为了能够将其接回链表中,我们需要获取 left 的前驱节点,和 right 的后驱节点。(LeetCode - 25. K 个一组翻转链表)
在这里插入图片描述

/**
* 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 reverseBetween(ListNode head, int left, int right) {
if(head == null || right == left){
return head;// 头节点为null,链表为空,反转链表没有意义(没有节点给你反转)
// right == left ,反转一个节点,等于没反转。也没有反转的意义
// 直接返回 head
}
ListNode newHead = new ListNode(0,head);
ListNode prev = newHead;
for(int i = 0; i < left - 1; i++){
prev = prev.next;
if(prev == null){// 防止空指针异常,另外防止 left 位置不合法(链表节点没有那么多)
return head;
}
}
ListNode rightNode = prev.next;
for(int i = 0;i < right - left;i++){
rightNode = rightNode.next;
if(rightNode == null){//防止空指针异常,另外防止 right 位置不合法(链表节点没有那么多)
return head;
}
}
ListNode rightNodeNext = rightNode.next;
ListNode[] reverse = myReverse(prev.next,rightNode);
prev.next = reverse[0];
rightNode = reverse[1];
rightNode.next = rightNodeNext;
return newHead.next;
}
public static ListNode[] myReverse(ListNode left,ListNode right){
ListNode prev = right.next;
ListNode p = left;
while( prev != right){
ListNode pNext = p.next;
p.next = prev;
prev = p;
p = pNext;
}
return new ListNode[]{right,left};
}
}

第三步:寻找 right 位置的节点

第五步: 敲写 myReverse 方法,(跟这题 LeetCode - 25. K 个一组翻转链表 一模一样)

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

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

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

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

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

发表评论