数据结构 Java DS——分享部分链表题目 (2)
目录
前言
题目一 —— 链表的回文结构
题目二 —— 二进制链表转整数
题目三 —— 设计链表
结尾
前言
关于JAVA的链表,笔者已经写了两篇博客来介绍了,今天给笔者们带来第三篇,也是分享了一些笔者写过的,觉得挺好的题目,链接也已经挂上了,笔者们可以去看看
入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)-CSDN博客
数据结构 Java DS——链表部分经典题目 (1)-CSDN博客
题目一 —— 链表的回文结构
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
鄙人在这分享一个最容易想到的思路吧,和之前判断数组是否回文的"双指针法"类似,不同的是这是一个单链表,我们这能获得下一个结点的地址而不能获得前一个,因此,你想到了什么?
没错,反转一下,我们将链表反转一下,然后对比他们是否是完全一致的,不是,return false;
以下是题解的代码
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
ListNode cur = A;
ListNode cur2 = reverseList(A);
while (cur != null && cur2 != null) {
if (cur.val != cur2.val) {
return false;
}
cur = cur.next;
cur2 = cur2.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode nextnode = cur.next;
cur.next = pre;
pre = cur;
cur = nextnode;
}
return pre;
}
}
不管是思路还是代码都很清晰,有助于锻炼思维,当然,也很基础
题目二 —— 二进制链表转整数
1290. 二进制链表转整数 - 力扣（LeetCode）
这道题笔者觉得,不但考察你对链表的理解,也考察你对于二进制转十进制这个基本知识的理解
笔者也分享一下笔者觉得最容易想到的思路,依据公式,我们都是从最右边的数开始算起,然后看他的位次决定他要和 "2的几次方" 相乘,最后得到和
那为何不反转这个链表,然后进行遍历,当遍历到非0的数时,进行运算,同时,用一个变量表示"2的权值",每次遍历完一个结点,就要指数就要+1
class Solution {
public int getDecimalValue(ListNode head)
{
ListNode head1=reverseList(head);
ListNode cur=head1;
int a=1;
int sum=0;
while(cur!=null)
{
if(cur.val==1)
{
sum+=a;
}
cur=cur.next;
a=a*2;
}
return sum;
}
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null)
{
ListNode nextnode=cur.next;
cur.next=pre;
pre=cur;
cur=nextnode;
}
return pre;
}
}请看代码,我们首先用a表示 2的n次幂 ,sum表示总和,每次符合条件就相加,不符合就跳过,但是2的质数一定是在加的,笔者在快速幂那一篇博客也提到过
数论, 一篇博客带你初识快速幂,已经为什么需要快速幂-CSDN博客
sum 就是最后的和
题目三 —— 设计链表
707. 设计链表 - 力扣（LeetCode）
这道题包含了了一些常见的链表操作,所以笔者觉得值得一写,可以提高我们对于链表的理解
class MyLinkedList {
public ListNode head;
public int usesize;
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public MyLinkedList() {
this.head = null;
this.usesize = 0;
}
public int get(int index) {
if (index < 0 || index >= usesize) {
return -1;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
ListNode listNode = new ListNode(val);
listNode.next = head;
head = listNode;
usesize++;
}
public void addAtTail(int val) {
ListNode listNode = new ListNode(val);
if (head == null) {
head = listNode;
} else {
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = listNode;
}
usesize++;
}
private ListNode findIndex(int idx) {
if (idx == 0) return null; // 对于 idx == 0，返回 null 作为前一个节点不存在的标志
ListNode cur = head;
for (int i = 0; i < idx - 1; i++) {
cur = cur.next;
}
return cur;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > usesize) {
return;
}
if (index == 0) {
addAtHead(val);
} else if (index == usesize) {
addAtTail(val);
} else {
ListNode temp = findIndex(index);
ListNode listNode = new ListNode(val);
listNode.next = temp.next;
temp.next = listNode;
usesize++;
}
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= usesize) {
return;
}
if (index == 0) {
head = head.next;
} else {
ListNode temp = findIndex(index);
temp.next = temp.next.next;
}
usesize--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/我们可以通过题解代码看到,这是一个很"系统"的代码,写的很完整,思路也不难,所以笔者就不做多余的说明了,代码应该写的很清楚
结尾
笔者还是会持续更新写过的题目,推荐给和笔者一样刚入门的初学者,请多多支持笔者,无收益写作,纯用爱发电.