当前位置：首页 > news >正文

数据结构 Java DS——分享部分链表题目 (2)

news 2025/5/26 8:14:40

前言

关于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 hereListNode 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);*/

我们可以通过题解代码看到,这是一个很"系统"的代码,写的很完整,思路也不难,所以笔者就不做多余的说明了,代码应该写的很清楚