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

前言

关于JAVA的链表,笔者已经写了两篇博客来先容了,今天给笔者们带来第三篇,也是分享了一些笔者写过的,觉得挺好的标题,链接也已经挂上了,笔者们可以去看看
入门数据结构JAVA DS——如何实现浅易的单链表(用JAVA实现)-CSDN博客
数据结构 Java DS——链表部分经典标题 (1)-CSDN博客

标题一   ——  链表的回文结构


链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

鄙人在这分享一个最轻易想到的思路吧,和之前判断数组是否回文的"双指针法"类似,不同的是这是一个单链表,我们这能获得下一个结点的地址而不能获得前一个,因此,你想到了什么?
没错,反转一下,我们将链表反转一下,然后对比他们是否是完全一致的,不是,return false;

以下是题解的代码

1. import java.util.*;
3. /*
4. public class ListNode {
5.     int val;
6.     ListNode next = null;
8.     ListNode(int val) {
9.         this.val = val;
10.     }
11. }*/
12. public class PalindromeList {
13.     public boolean chkPalindrome(ListNode A) {
14.         // write code here
15.         ListNode cur = A;
16.         ListNode cur2 = reverseList(A);
17.         while (cur != null && cur2 != null) {
18.             if (cur.val != cur2.val) {
19.                 return false;
20.             }
21.             cur = cur.next;
22.             cur2 = cur2.next;
23.         }
24.         return true;
25.     }
26.     private ListNode reverseList(ListNode head) {
27.         if (head == null) {
28.             return null;
29.         }
30.         ListNode pre = null;
31.         ListNode cur = head;
32.         while (cur != null) {
33.             ListNode nextnode = cur.next;
34.             cur.next = pre;
35.             pre = cur;
36.             cur = nextnode;
37.         }
38.         return pre;
39.     }
40. }

复制代码

不管是思路还是代码都很清晰,有助于锻炼头脑,固然,也很基础



标题二    ——  二进制链表转整数       

1290. 二进制链表转整数 - 力扣（LeetCode）
这道题笔者觉得,不光考察你对链表的理解,也考察你对于二进制转十进制这个基本知识的理解

笔者也分享一下笔者觉得最轻易想到的思路,依据公式,我们都是从最右边的数开始算起,然后看他的位次决定他要和 "2的几次方" 相乘,末了得到和
那为何不反转这个链表,然后举行遍历,当遍历到非0的数时,举行运算,同时,用一个变量体现"2的权值",每次遍历完一个结点,就要指数就要+1

1. class Solution {
2.     public int getDecimalValue(ListNode head)
3.     {
4.      ListNode head1=reverseList(head);
5.      ListNode cur=head1;
6.     int a=1;
7.     int sum=0;
9.      while(cur!=null)
10.      {
11.         if(cur.val==1)
12.         {
13.               sum+=a;
14.         }
15.         cur=cur.next;
16.         a=a*2;
17.      }
18.      return sum;
19.     }
20. public ListNode reverseList(ListNode head) {
21. ListNode pre=null;
22. ListNode cur=head;
23. while(cur!=null)
24. {
25.    ListNode nextnode=cur.next;
26.    cur.next=pre;
27.    pre=cur;
28.    cur=nextnode;
29. }
30. return pre;
31. }
32. }

复制代码

请看代码,我们起首用a体现 2的n次幂 ,sum体现总和,每次符合条件就相加,不符合就跳过,但是2的质数一定是在加的,笔者在快速幂那一篇博客也提到过

数论, 一篇博客带你初识快速幂,已经为什么必要快速幂-CSDN博客

sum 就是末了的和

标题三  —— 计划链表

707. 计划链表 - 力扣（LeetCode）

 这道题包罗了了一些常见的链表操作,以是笔者觉得值得一写,可以提高我们对于链表的理解

1. class MyLinkedList {
2.     public ListNode head;
3.     public int usesize;
5.     static class ListNode {
6.         int val;
7.         ListNode next;
9.         public ListNode(int val) {
10.             this.val = val;
11.         }
12.     }
14.     public MyLinkedList() {
15.         this.head = null;
16.         this.usesize = 0;
17.     }
19.     public int get(int index) {
20.         if (index < 0 || index >= usesize) {
21.             return -1;
22.         }
23.         ListNode cur = head;
24.         for (int i = 0; i < index; i++) {
25.             cur = cur.next;
26.         }
27.         return cur.val;
28.     }
30.     public void addAtHead(int val) {
31.         ListNode listNode = new ListNode(val);
32.         listNode.next = head;
33.         head = listNode;
34.         usesize++;
35.     }
37.     public void addAtTail(int val) {
38.         ListNode listNode = new ListNode(val);
39.         if (head == null) {
40.             head = listNode;
41.         } else {
42.             ListNode cur = head;
43.             while (cur.next != null) {
44.                 cur = cur.next;
45.             }
46.             cur.next = listNode;
47.         }
48.         usesize++;
49.     }
51.     private ListNode findIndex(int idx) {
52.         if (idx == 0) return null;  // 对于 idx == 0，返回 null 作为前一个节点不存在的标志
53.         ListNode cur = head;
54.         for (int i = 0; i < idx - 1; i++) {
55.             cur = cur.next;
56.         }
57.         return cur;
58.     }
60.     public void addAtIndex(int index, int val) {
61.         if (index < 0 || index > usesize) {
62.             return;
63.         }
64.         if (index == 0) {
65.             addAtHead(val);
66.         } else if (index == usesize) {
67.             addAtTail(val);
68.         } else {
69.             ListNode temp = findIndex(index);
70.             ListNode listNode = new ListNode(val);
71.             listNode.next = temp.next;
72.             temp.next = listNode;
73.             usesize++;
74.         }
75.     }
77.     public void deleteAtIndex(int index) {
78.         if (index < 0 || index >= usesize) {
79.             return;
80.         }
81.         if (index == 0) {
82.             head = head.next;
83.         } else {
84.             ListNode temp = findIndex(index);
85.             temp.next = temp.next.next;
86.         }
87.         usesize--;
88.     }
89. }
91. /**
92. * Your MyLinkedList object will be instantiated and called as such:
93. * MyLinkedList obj = new MyLinkedList();
94. * int param_1 = obj.get(index);
95. * obj.addAtHead(val);
96. * obj.addAtTail(val);
97. * obj.addAtIndex(index,val);
98. * obj.deleteAtIndex(index);
99. */

复制代码

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


结尾


笔者还是会持续更新写过的标题,推荐给和笔者一样刚入门的初学者,请多多支持笔者,无收益写作,纯用爱发电.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。