剑指Offer之Java算法习题精讲链表专题篇
题目一
解法
/**
* 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 int getDecimalValue(ListNode head) {
int[] arr = new int[31];
int index = 0;
int ans = 0;
while(head!=null){
arr[index] = head.val;
index++;
head = head.next;
}
for(int i = 0;i<index;i++){
if(arr[i]==1){
ans+=(1<<(index-1-i));
}
}
return ans;
}
}
题目二
解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
int index = 0;
ListNode h = head;
while(head!=null){
head = head.next;
index++;
}
int[] arr = new int[index];
while(h!=null){
arr[index-1] = h.val;
index--;
h = h.next;
}
return arr;
}
}
题目三
解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode node = new ListNode(-1);
ListNode ans = node;
while(l1!=null&&l2!=null){
if(l1.val<=l2.val){
node.next = l1;
l1 = l1.next;
}else{
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
if(l1!=null){
node.next = l1;
}
if(l2!=null){
node.next = l2;
}
return ans.next;
}
}
到此这篇关于剑指Offer之Java算法习题精讲链表专题篇的文章就介绍到这了,更多相关Java 链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java 详解分析链表的中间节点
目录 1.题目描述 2.解法 3.复杂度 1.题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点. 如果有两个中间结点,则返回第二个中间结点. 题目来源:力扣(LeetCode) 2.解法 定义一个快指针 fast 和一个慢指针 slow :fast 走两步, slow 走一步,当 fas t走到尽头时, slow 就刚好在中间节点.因为 fast 比slow 多走一半路程 class Solution { public ListNode middleNode(ListNod
-
Java 数据结构与算法系列精讲之单向链表
目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表
-
Java 精炼解读数据结构的链表的概念与实现
目录 前言: 一.什么是链表 链表的概念 链表的结构 链表如何存储数据 链表的实现 穷举法创建链表 打印链表 查找是否包含关键字key是否在单链表当中 得到单链表的长度: 头插法 尾插法 任意位置插入,第一个数据节点为0号下标 删除第一次出现关键字为key的节点 删除所有值为key的节点 总结: 前言: 顺序表的问题及思考 1. 顺序表中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间.会有不小的消耗. 3. 增容一般是呈2倍的增长,势必会有一定的空
-
Java 详解如何从尾到头打印链表
目录 1.题目 2.解法 2.1栈 2.2递归 3.复杂度 3.1栈 3.2递归 1.题目 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回). 题目来源:力扣(LeetCode) 2.解法 2.1栈 栈的特点是先进后出,所以我们创建一个栈,逐个将节点压入栈内,然后建立一个数组,将栈内的节点数值逐个弹出 class Solution { public int[] reversePrint(ListNode head) { Stack<ListNode> stack = new
-
Java 数据结构与算法系列精讲之环形链表
目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li
-
Java关于重排链表详细解析
1.题目 给定一个单链表 L 的头节点 head ,单链表 L 表示为: L0→ L1 → - → Ln-1 → Ln 请将其重新排列后变为: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → - 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换. 来源:力扣(LeetCode) 2.解析 将一个链表分为两个子链表,然后将其归并. 我们要先找到链表的中间节点,在中间节点将其断开 然后反转后半链表 再将两个子链表逐个连起来 将后半链表反转,独立成一个子链表. 最
-
Java实现单链表基础操作
关于链表 链表是有序的列表链表是以节点的方式来存储每个节点包含data域,next域(指向下一个节点)分带头节点的链表和没有头节点的链表 定义一个节点: package linkedQueue; public class HeroNode { public int no; public String name; public String nickname; public HeroNode next;//指向下一个节点 public HeroNode(int no, String name, S
-
Java实现顺序表和链表结构
目录 前言: 顺序表 定义: 实现方法: 代码实现: 链表 定义: 分类: 实现方法: 代码实现: 顺序表 & 链表 总结 前言: 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串. 顺序表 定义: 用一段物理地址连续的存储单元依次存储数据元素的线性结构(逻辑上连续,物理上也连续) (1)静态顺序表:使用定长数组存储. (2)动态顺序表:使用动态开辟的数组存储 [注意]静态顺序表的定长数
-
Java复杂链表的复制详解
目录 1.题目 2.解法 2.1 拼接+拆分 3.代码 1.题目 请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 2.解法 2.1 拼接+拆分 首先我们逐个将节点复制并且和原来的链表连起
-
剑指Offer之Java算法习题精讲链表专题篇
题目一 解法 /** * 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 Solut
-
剑指Offer之Java算法习题精讲二叉树专题篇下
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *
-
剑指Offer之Java算法习题精讲二叉树专题篇上
来和二叉树玩耍吧~ 题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val
-
剑指Offer之Java算法习题精讲链表与字符串及数组
题目一 解法 /** * 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 Soluti
-
剑指Offer之Java算法习题精讲链表专项训练
题目一 链表题--链表合并 根据给定的两个升序链表合并为一个新的升序链表 具体题目如下 解法 /** * 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;
-
剑指Offer之Java算法习题精讲链表与数组专项训练
题目一 数组题——查找目标值 在给定的数组中查找指定的目标值,这里提供两种解法 具体题目如下 解法一 class Solution { public int[] twoSum(int[] nums, int target) { int[] a = {-1,-1}; for(int i = 0;i<nums.length-1;i++){ for(int j = i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ a[0] = i; a[1]
-
剑指Offer之Java算法习题精讲链表与二叉树专项训练
题目一 链表题——反转链表 根据单链表的头节点head来返回反转后的链表 具体题目如下 解法 /** * 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;
-
剑指Offer之Java算法习题精讲二叉树与斐波那契函数
题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二 解法 /** * Definition for a binary tree node. * public class TreeNode { * in
-
剑指Offer之Java算法习题精讲二叉树与N叉树
题目一 解法 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; *
-
剑指Offer之Java算法习题精讲数组与字符和等差数列
题目一 解法 class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int[] arr = new int[1001]; int[] ans = new int[arr1.length]; int index = 0; for(int i =0;i<arr1.length;i++){ arr[arr1[i]]+=1; } for(int i = 0;i<arr2.length;i++){ while