[数据结构] ArrayList(顺序表)与LinkedList(链表)

目录

1.List

1.1 什么是List

1.2 常用的方法

1.3 List的使用

2. 线性表

3. ArrayList 类(顺序表)

3.1 顺序表定义

3.2 ArrayList链表的功能模拟实现

3.3 ArrayList简介

3.4 ArrayList的构造方法

3.5 ArrayList的遍历

3.5 ArrayList的具体使用实例

3.5.1 杨辉三角

3.5.2 简单的洗牌算法

4. LinkedList 类(链表）

4.1 链表的概念

4.2 无头单向非循环链表的功能模拟实现

4.3 LinkedList链表

4.3.1 LinkedList链表的概念

4.3.2 LinkedList链表的功能模拟实现

4.3.3 LinkedList链表的构造方法

4.3.4 LinkedList链表的遍历

4.4 链表的练习题

1.List

1.1 什么是List

List是一个接口，继承于Collection，Collection也是一个接口，Collection类继承于Iterable，Iterable也是一个接口。

Collection接口规范了一些常用的方法。

实现Iterable接口的类可以逐个元素遍历：

在数据结构层次来看，List就是一个线性表，是一组具有相同数据类型的数据的有序序列，在这个有序序列上可以进行增删改查以及变量等操作。

1.2 常用的方法

下面是List类里面常用的方法：

1.3 List的使用

List是一个接口，里面包含了很多抽象方法，要调用这些方法，需要实现该接口，并且要重写这些方法，比如说ArrayList和LinkedList就实现了List接口。

2. 线性表

线性表是一组具有相同数据类型的数据的有序序列，线性表是一种常用的数据结构，包括：顺序表，链表，栈，队列等。

线性表在逻辑上是线性结构，也就是一条连续的直线，但是在物理结构上线性表不一定是连续的，

线性表的主要存储方式：数组和链表。

                                                                        顺序表

                                                                        链表

3. ArrayList 类(顺序表)

3.1 顺序表定义

顺序表是一组物理地址连续的空间用来存储数据，一般来说是用数组来存储，对数组进行增删改查。

3.2 ArrayList链表的功能模拟实现

这里我自己对ArraysList里面的方法进行了实现：

public class MyArrayList implements IList {public int[] arr;public int arrTrueSize;private static final int ARR_SIZE = 5;public MyArrayList() {arr = new int[ARR_SIZE];}public MyArrayList(int size) {arr = new int[size];}//添加元素到最后一个位置@Overridepublic void add(int data) {//判断数组是否已满if(isFull()) {//扩容grow();}arr[arrTrueSize] = data;arrTrueSize++;}//2倍扩容private void grow() {arr = Arrays.copyOf(arr,2*ARR_SIZE);}//在指定pos位置添加元素@Overridepublic void add(int pos, int data) {checkPosOfAdd(pos);//如果数组满了if(isFull()) {grow();}for(int i = arrTrueSize - 1; i >= pos; i--) {arr[i+1] = arr[i];}arr[pos] = data;arrTrueSize++;}//检查pos范围是否正常private void checkPosOfAdd(int pos) {if(pos < 0 || pos > arrTrueSize) {throw new PosOutOfBoundsException("添加元素位置的pos不合法，请重新输入" + pos);}}//判断是否包含某元素@Overridepublic boolean contains(int toFind) {for (int i = 0; i < arrTrueSize; i++) {if(arr[i] == toFind) {return true;}}return false;}//查找某个元素对应的下标@Overridepublic int indexOf(int toFind) {for (int i = 0; i < arrTrueSize; i++) {if(arr[i] == toFind) {return i;}}return -1;}//获取pos位置对应的元素@Overridepublic int get(int pos) {checkPosOfGetOrSet(pos);if(isEmpty()) {throw new ListEmptyException("获取元素时，顺序表为空");}return arr[pos];}//判断get方法中的pos范围是否合法private void checkPosOfGetOrSet(int pos) {if(pos < 0 || pos >= arrTrueSize) {throw new PosOutOfBoundsException("获取或者设置元素位置的pos不合法" + pos);}}//设置pos位置的元素为value@Overridepublic void set(int pos, int value) {checkPosOfGetOrSet(pos);arr[pos] = value;}//删除第一次出现的元素@Overridepublic void remove(int toRemove) {int index = indexOf(toRemove);if(index == -1) {System.out.println("没有你要删除的元素");}for (int i = index; i < arrTrueSize - 1; i++) {arr[i] = arr[i+1];}arrTrueSize--;}//获取顺序表里面的数据数量@Overridepublic int size() {return arrTrueSize;}//清空顺序表@Overridepublic void clear() {arrTrueSize = 0;}@Overridepublic void display() {for (int i = 0; i < arrTrueSize; i++) {System.out.print(arr[i] + " ");}System.out.println();}//判断顺序表是否满了@Overridepublic boolean isFull() {return arrTrueSize == arr.length;}//判断顺序表是否为空@Overridepublic boolean isEmpty() {return arrTrueSize == 0;}
}

这里我没有用泛型的方式来实现，实际上系统的ArraysList是用的泛型类，使用之前需要先进行实例化。

3.3 ArrayList简介

下面是ArrayList类实现的接口和继承的抽象类：

绿色是抽象类，粉色是类，其他是接口

这里ArrayList实现了RandomAccess接口，表明ArraysList支持随机访问。

ArrayList实现Cloneable接口，表示ArraysList可以clone。

ArrayList实现Serializable接口，表示ArraysList支持序列化。

ArrayList在单线程下可以使用，在多线程选择1使用Vector或者CopyOnWriteArrayList

ArrayList底层是一段连续的空间，可以进行动态扩容，是一个动态类型的顺序表。

3.4 ArrayList的构造方法

ArrayList存在三个构造方法，构成方法的重载。

无参数的构造方法源代码为：

调用空参数的构造方法时，会创建一个空的数组，那么如何add呢

这里我们查看add的底层代码：

这里又调用了add方法：

下面代码说明如果数组为空就调用grow方法来扩容。

grow方法源码：

上面代码意思是当数组大小为0时调用else里面的代码，创建一个大小为10的数组。当大小为10的数组满了就1.5倍扩容。

总结：所以调用无参数的构造方法时，首次添加元素时要调用grow方法扩容为10。

参数是一个指定大小的数的构造方法源码是：

下面会根据你传入的数据来创建对应大小的顺序表。

参数是Collection类型或者其子类类型的构造方法的源码为：

这里面的参数可以是Collection类型或者其子类类型。

比如说：

输出结果为：

3.5 ArrayList的遍历

这里有三种遍历方式：for循环，for-each循环，迭代器。

代码如下：

 public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);//for循环for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + " ");}System.out.println();//for-each循环for(Integer integer : arrayList) {System.out.print(integer + " ");}System.out.println();//迭代器Iterator<Integer> it = arrayList.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}}

迭代器相当于将数组里面的元素依次打印出来。

只要是实现了Iterable接口，就可以用迭代器遍历。

3.5 ArrayList的具体使用实例

3.5.1 杨辉三角

给定一个非负数num(1 <= num <= 30),输出前num层的杨辉三角。

这里我们可以转换成这样来看：

这里我们发现除了第一行，其他的每行的第一个元素和最后一个元素都是1，这里我们可以先把第一行设置出来。然后再从第二行开始逐行进行设置，每行的第一个和最后一个为1，

中间的数=该数的上一行的上一列的数+该数上一行的这一列的数，根据此规律写出中间的数。

最后代码如下：

    public static List<List<Integer>> generate(int num) {List<List<Integer>> list1 = new ArrayList<>();//先处理第一行元素List<Integer> list2 = new ArrayList<>();list2.add(1);list1.add(list2);//下面一行一行处理for (int i = 1; i < num; i++) {List<Integer> list3 = new ArrayList<>();//处理第一个元素为1list3.add(1);//处理中间for (int j = 1; j < i; j++) {int a = list1.get(i-1).get(j-1) +list1.get(i-1).get(j);list3.add(a);}//处理最后一个元素为1list3.add(1);list1.add(list3);}return list1;}

3.5.2 简单的洗牌算法

这里我们需要先生成52张牌，然后将牌打乱，再三个人轮流拿五张牌。

我这里打乱是利用最后一张牌跟前面随机的一张牌交换顺序，直到交换到第一张牌停止。

代码如下：
 

public class Test02 {String[] arr = {"♣","♦","♥","♠"};//生成一副牌public List<Card> createCards() {List<Card> cards = new ArrayList<>(52);for (int i = 0; i < 4; i++) {for (int j = 0; j < 13; j++) {String cardShape = arr[i];int cardSize = j;Card card = new Card();card.cardSize = cardSize;card.cardShape = cardShape;cards.add(card);}}return cards;}//打乱牌(将最后一张牌与前面的牌随机抽取一张交换,从后往前直到第一张牌)private void shuffle(List<Card> cards) {Random random = new Random();for (int i = cards.size() - 1; i > 0; i--) {int n = random.nextInt(i);swap(cards,i,n);}}//交换牌public void swap(List<Card> cards, int a, int b) {Card card = cards.get(a);cards.set(a,cards.get(b));cards.set(b,card);}public static void main(String[] args) {Test02 test02 = new Test02();List<Card> cards = test02.createCards();System.out.println(cards);System.out.println();//打乱牌test02.shuffle(cards);System.out.println(cards);System.out.println();//三个人轮流抓五张牌List<List<Card>> list = new ArrayList<>(3);list.add(new ArrayList<>());list.add(new ArrayList<>());list.add(new ArrayList<>());for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {list.get(j).add(cards.remove(0));}}System.out.println("A:");System.out.println(list.get(0));System.out.println("B:");System.out.println(list.get(1));System.out.println("C:");System.out.println(list.get(2));}
}

4. LinkedList 类(链表）

4.1 链表的概念

链表是一种物理存储结构上非连续的存储结构。

链表结构非常多：

单向或双向：

单向

双向

带头或不带头：

        带头

不带头

循环或非循环：

非循环

循环

我们主要学习两种：无头单向非循环列表 和 无头双向循环列表。

无头双向循环列表是LinkedList类的实现方式。

4.2 无头单向非循环链表的功能模拟实现

下面是我自己实现的无头单向非循环链表的功能

public class MySingleList {//节点类(静态内部类)static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//创建一个链表public void createLinkedList() {ListNode listNode1 = new ListNode(11);ListNode listNode2 = new ListNode(22);ListNode listNode3 = new ListNode(33);ListNode listNode4 = new ListNode(44);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;this.head = listNode1;}//头插法public void addFirst(int data){ListNode listnode = new ListNode(data);listnode.next = head;head = listnode;}//尾插法public void addLast(int data){ListNode listNode = new ListNode(data);if(head == null) {head = listNode;}//找到最后一个位置插入ListNode node = head;while(node != null) {if(node.next == null) {node.next = listNode;return;}node = node.next;}}//任意位置插⼊,第⼀个数据节点为0号下标public void addIndex(int index,int data){int len = size();if(index < 0 || index > len - 1) {return;}//头插法if(index == 0) {addFirst(data);return;}//尾插法if(index == len - 1) {addLast(data);return;}//中间插入ListNode node = new ListNode(data);ListNode newHead = head;//获取插入位置的上一个节点ListNode cur = findBeginList(index);if(cur == null) {return;}node.next = cur.next;cur.next = node;}//找到插入位置的前一个节点private ListNode findBeginList(int index) {int len = size();if(index < 0 || index > len - 1) {return null;}ListNode node = head;int i = 0;while(i != index - 1) {node = node.next;i++;}return node;}//查找关键字key是否在单链表当中public boolean contains(int key){ListNode node = head;while(node != null) {if(node.val == key) {return true;}node = node.next;}return false;}//删除第⼀次出现关键字为key的节点public void remove(int key){if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode val = findBeginNumList(key);if(val == null) {return;}ListNode cul = val.next.next;head.next = cul;}//查找关键字的前驱节点public ListNode findBeginNumList(int key) {if(head == null) {return null;}ListNode node = head;while(node.next != null) {if(node.next.val == key) {return node;}node = node.next;}return null;}//删除所有值为key的节点public void removeAllKey(int key){if(head == null) {return;}//删除所有key节点ListNode cul = head;ListNode pex = cul.next;while(pex != null) {if(pex.val == key) {cul.next = pex.next;pex = pex.next;}else {cul = cul.next;pex = pex.next;}}//判断第一个元素是否需要删除if(head.val == key) {head = head.next;}}//得到单链表的⻓度public int size(){ListNode node = head;int listNum = 0;while(node != null) {listNum++;node = node.next;}return listNum;}public void clear() {}//打印链表public void display() {ListNode node = head;while(node != null) {System.out.print(node.val + " ");node = node.next;}System.out.println();}//从指定节点打印链表public void display(ListNode listNode) {ListNode node = listNode;while(node != null) {System.out.println(node.val + " ");node = node.next;}System.out.println();}
}

4.3 LinkedList链表

4.3.1 LinkedList链表的概念

LinkedList链表底层是无头双向不循环链表，利用这种方法对链表的增删查改操作比较方便。

LinkedList 实现了List接口，在任意位置的插入删除操作效率比较高，时间复杂度为O(1)。

4.3.2 LinkedList链表的功能模拟实现

下面是我自己实现的LinkedList类里面的功能:

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}//标记的头节点public ListNode head;//标记的尾节点public ListNode last;//头插法public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;last = node;return;}node.next = head;head.prev = node;head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;last = node;return;}last.next = node;node.prev = last;last = node;}//指定index位置插入public void addIndex(int index, int data) {int size = size();if(index < 0 || index > size) {System.out.println("下标输入错误" + index);return;}//头插法if(index == 0) {addFirst(data);return;}//尾插法if(index == size) {addLast(data);return;}//中间插入ListNode cul = new ListNode(data);ListNode pex = head;while(index != 0) {pex = pex.next;index--;}cul.next = pex;pex.prev.next = cul;cul.prev = pex.prev;pex.prev = cul;}//查找关键字key是否在单链表中public boolean contains(int key) {ListNode node = head;while(node != null) {if(node.val == key) {return true;}node = node.next;}return false;}//删除单链表中第一次出现key的节点public void remove(int key) {ListNode node = head;while(node != null) {if(node.val == key) {//判断是否是删除第一个节点if(node.prev == null) {if(node.next == null) {head = null;last = null;}else {node.next.prev = null;head = node.next;}}else {//判断是否删除最后一个节点if(node.next == null) {node.prev.next = null;last = node.prev;}else {//删除中间节点node.prev.next = node.next;node.next.prev = node.prev;}}break;}node = node.next;}}//删除单链表中所有的key的节点public void removeAllKey(int key) {ListNode node = head;while(node != null) {if(node.val == key) {//判断是否是删除第一个节点if(node.prev == null) {if(node.next == null) {head = null;last = null;}else {node.next.prev = null;head = node.next;}}else {//判断是否删除最后一个节点if(node.next == null) {node.prev.next = null;last = node.prev;}else {//删除中间节点node.prev.next = node.next;node.next.prev = node.prev;}}}node = node.next;}}//打印链表public void display() {ListNode node = head;while(node != null) {System.out.print(node.val + " ");node = node.next;}System.out.println();}//求链表的长度public int size() {ListNode node = head;int num = 0;while(node != null) {num++;node = node.next;}return num;}//清除单链表public void clear() {ListNode node = head;while(node != null) {ListNode nodeN = node.next;node.prev = null;node.next = null;node = nodeN;}head = null;last = null;}
}

4.3.3 LinkedList链表的构造方法

LinkedList有两个构造方法：

第二个构造方法是利用另一个链表来创建链表：

        LinkedList<Integer> list1 = new LinkedList<>();list1.add(11);list1.add(22);list1.add(33);LinkedList<Integer> list2 = new LinkedList<>(list1);System.out.println(list2);

4.3.4 LinkedList链表的遍历

    public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(11);list1.add(22);list1.add(33);//方法1：System.out.println(list1);//方法2:for (int i = 0; i < list1.size(); i++) {System.out.print(list1.get(i) + " ");}System.out.println();//方法3：for(int i : list1) {System.out.print(i + " ");}System.out.println();//方法4(迭代器)正向遍历：ListIterator<Integer> it = list1.listIterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();//迭代器反向遍历:ListIterator<Integer> itN = list1.listIterator(list1.size());while(itN.hasPrevious()) {System.out.print(itN.previous() + " ");}}

4.4 链表的练习题

1.删除链表中等于给定值val的所有节点

题目链接

解题思路：

这里我利用了两个下标：cul作为第一个位置的地址，pex作为第二个位置的地址，判断pex的值是否为删除的值key, 如果是，则删除，cur指向pex的下一位，然后pex后移一位，如果不是，则cul和pex统一后移一位再进行判断。最后再检查第一位的值是否为key。

代码实现：

/*** 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 removeElements(ListNode head, int key) {ListNode newHead = head;if(newHead == null) {return null;}//删除所有的key元素ListNode cul = newHead;ListNode pex = cul.next;while(pex != null) {if(pex.val == key) {cul.next = pex.next;pex = pex.next;}else {cul = cul.next;pex = pex.next;}}//判断第一个元素是否是keyif(head.val == key) {head = head.next;}return head;}
}

2. 反转一个单链表

题目链接

第一种：

解题思路：

这里利用了递归的想法，想要n长度的链表反转，必须要后n-1长度链表反转，依次类推直到最后链表长度为1，返回最后一个数据的地址，将长度为2的链表反转。

代码实现：

/*** 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 reverseList(ListNode head) {if(head ==  null) {return head;}if(head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

第二种：

解题思路：

这里利用了循环的思路，创建一个变量cur作为head的下一个节点，变量pex作为cur的下一个节点，先将第二个节点的next换成第一个节点的地址，然后把三个变量依次后移，循环往复。

代码实现：

/*** 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 reverseList(ListNode head) {if(head == null) {return head;}if(head.next == null) {return head;}ListNode cur = head.next;head.next = null;while(cur != null) {ListNode pex = cur.next;cur.next = head;head = cur;cur = pex;}return head;}
}

3. 给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

题目链接

解题思路：这里用到了快慢指针法，设置两个指针slow和fast，根据相同路程，二倍的速度行驶的距离也是二倍，当fast到达链表最后时，slow刚好到达链表中间。

代码实现：

/*** 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 middleNode(ListNode head) {if(head == null) {return head;}if(head.next == null) {return head;}ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

4. 输入一个链表，输出该链表中倒数第k个结点。

题目链接

方法1：

解题思路：求倒数第k个节点，也就是求正数第len +1 - k个节点，len是链表的长度。

代码实现：

/*** 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 kthToLast(ListNode head, int k) {ListNode node = head;//求链表长度int len = 0;while(node != null) {node = node.next;len++;}for(int i = 1; i < len+1-k; i++) {head = head.next;}return head.val;}
}

方法2：

解题思路：

我们可以定义两个下标slow和fast，让fast比slow先走k-1步，它们之间距离就差k-1步，这样当fast走到最后一个节点时候，slow刚好就是倒数第k个节点，因为slow和fast之间的距离不变。

求倒数第k个节点，相当于倒数第k个节点跟最后一个节点差了k-1步。

代码实现：

/*** 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 kthToLast(ListNode head, int k) {ListNode slow = head;ListNode fast = head;int i = 0;while(i < k-1) {fast = fast.next;i++;}while(fast.next != null) {slow = slow.next;fast = fast.next;}return slow.val;}
}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目链接

解题思路：这里是设置一个中转节点head，再设置一个节点cul指向head，然后判断list1.val和list2.val的大小，让cul指向小的，以此类推，最后返回中间结点的next。

代码实现：

/*** 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 mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode(-1);ListNode cul = newHead;while(list1 != null && list2 != null) {if(list1.val < list2.val) {cul.next = list1;list1 = list1.next;}else {cul.next = list2;list2 = list2.next;}cul = cul.next;}if(list1 == null) {cul.next = list2;}if(list2 == null) {cul.next = list1;}return newHead.next;}
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

题目链接

解题思路：这题可以先创建两个链表，list1用来存储比x小的节点，list2用来存储比x大的节点。最后将两个节点拼接起来。要考虑到所有数都比x大，所有数比x都小，list2节点不为空的话最后一个节点的next是否置为null。

代码实现：

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {      ListNode list1 = new ListNode(-1);ListNode list2 = new ListNode(-2);ListNode newHead1 = list1;ListNode newHead2 = list2;while(pHead != null) {if(pHead.val < x) {list1.next = pHead;list1 = list1.next;}else {list2.next = pHead;list2 = list2.next;}pHead = pHead.next;}if(newHead1.next == null) {return newHead2.next;}list1.next = newHead2.next;//将最后一个节点的next换为nullif(newHead2 != null) {list2.next = null;}return newHead1.next;}
}

7. 链表的回文结构。

题目链接      回文结构是指以中心点为分割线两边的数值对称相等。

解题思路：

这道题我们可以按照先找到链表的中间位置，然后将后半部分回转，再从两边向中间靠拢，检查val是否相同，因为终止条件是左边的head与右边的slow相等时终止，但是偶数的话不会相等，我们可以通过判断它们紧挨着时候上一个节点的next是否等于下一个节点，相等返回true。

代码实现：

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode head) {if(head == null) {return false;}if(head.next == null) {return true;}//先找到中间位置ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}//将中间位置后面的节点逆置ListNode cul = slow.next;slow.next = null;while(cul != null) {ListNode pex = cul.next;cul.next = slow;slow = cul;cul = pex;}//从两边开始判断while(head != slow) {if(head.val != slow.val) {return false;}if(head.next == slow) {return true;}head = head.next;slow = slow.next;}return true;}
}

8. 输入两个链表，找出它们的第一个公共结点。

题目链接

解题思路：如果两条链表长度不同，我们可以先求出长的链表比短的链表长多少，让长的链表先走的跟短的链表一个起点，然后一起走。

代码实现：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode sho = headA;ListNode lon = headB;int len1 = 0;int len2 = 0;while(sho != null) {sho = sho.next;len1++;}sho = headA;while(lon != null) {lon = lon.next;len2++;}lon = headB;int len = len2 - len1;if(len1 > len2) {sho = headB;lon = headA;len = len1 - len2;}int i = 0;while(i < len) {lon = lon.next;i++;}while(sho != lon) {sho = sho.next;lon = lon.next;}return lon;}
}

9. 给定⼀个链表，判断链表中是否有环

题目链接

解题思路：这里利用了快慢下标法,设置慢下标slow和快下标fast，slow每次走一格，fast每次走两格，这样fast比slow每次多增加一格，这样的话，如果链表有环，则fast和slow不会错过，链表有偶数个数据时，fast!=null，当链表有奇数个数据时，fast.next!=null。

代码实现：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {return true;}}return false;}
}

10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回NULL

题目链接

解题思路：这里可以证明得从起始点到入口点的距离等于从相遇点到入口点的距离。然后两个节点分别从起始点和相遇点走，相遇的时候就是入口点。

代码实现:

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//判断是否有环，并找到相遇点的节点ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {break;}}if(fast == null || fast.next == null) {return null;}fast = head;while(fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}

注意：以上题目是博主写的其中一种解题方法，仅供参考，还有其他方法可以自行去了解。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/95910.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/95910.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Hive使用Tez引擎出现OOM的解决方法

Hive使用Tez引擎出现OOM的解决方法

环境是Hive以Tez作为引擎&#xff0c;然后使用客户端&#xff08;比如DataGrip&#xff09;连接Hive运行SQL查询&#xff0c;运行过程中报错信息如下&#xff1a;java.lang.OutOfMemoryError: Java heap space…连接工具以DataGrip为例&#xff0c;解决办法如下&#xff1a; --…
阅读更多...
SQL面试题及详细答案150道（81-100） --- 子查询篇

SQL面试题及详细答案150道（81-100） --- 子查询篇

《前后端面试题》专栏集合了前后端各个知识模块的面试题，包括html，javascript，css，vue，react，java，Openlayers，leaflet，cesium，mapboxGL，threejs，nodejs，mangoDB，MySQL，Linux… 。 前后端面试题-专栏总目录 文章目录 一、本文面试题目录 81. 什么是子查询？子查…
阅读更多...
笔记：ubuntu安装matlab

笔记：ubuntu安装matlab

记录一下ubuntu安装matlab的过程 一、进入桌面 虽然系统是ubuntu server&#xff0c;但是安装matlab最好还是有桌面。这里使用todesk等工具&#xff0c;进入桌面进行远程安装。 二、创建matlab账号 由于学校已经提供了matlab的账号&#xff0c;只需要用自己的学生邮箱进行注册即…
阅读更多...
CentOS 7 编译安装 OpenSSL 3.4.2

CentOS 7 编译安装 OpenSSL 3.4.2

CentOS 7默认已经安装了OpenSSL&#xff0c;不过版本比较低 openssl version结果为&#xff1a;OpenSSL 1.0.2k-fips 26 Jan 2017 已经无法满足需求 OpenSSL 源码下载链接&#xff1a;https://www.openssl-library.org/source/ 下载源码包为&#xff1a;https://github.com…
阅读更多...
python advance -----object-oriented

python advance -----object-oriented

alt shift 上下键&#xff0c;行代码上下移动0
阅读更多...
具身智能的工程落地：视频-控制闭环的实践路径

具身智能的工程落地：视频-控制闭环的实践路径

引言&#xff1a;从“能算会说”到“会看能做” 具身智能真正的门槛&#xff0c;不在于把模型做得更大&#xff0c;而在于把感知—决策—执行焊成一条低时延、稳态可控的闭环工程链路&#xff1a;从相机/麦克风采集&#xff0c;到编解码与传输&#xff0c;再到边/端推理、指令…
阅读更多...
STM32 - Embedded IDE - GCC - 如何在工程中定义一段 NoInit RAM 内存

STM32 - Embedded IDE - GCC - 如何在工程中定义一段 NoInit RAM 内存

导言如上所示&#xff0c;Keil创建一段NoInit内存同样是通过图形界面来完成&#xff0c;IRAM2的起始地址0x2000000&#xff0c;大小8bytes。NoInit的意思是程序初始化时&#xff0c;不会将内存清0初始化。如上所示&#xff0c;在MEMORY段&#xff0c;将64K的RAM内存划一块8byte…
阅读更多...
MyBatisX代码生成插件在IDEA中的安装配置、连接数据库表生成代码快速开发示例

MyBatisX代码生成插件在IDEA中的安装配置、连接数据库表生成代码快速开发示例

场景 MyBatisX插件介绍 MybatisX是一款基于IDEA的快速开发插件&#xff0c;由MyBatis-Plus团队开发维护&#xff0c;为效率而生。 它的主要功能如下&#xff1a; 支持mapper.xml和Mapper接口之间方法的互相导航跳转&#xff1b; 内置代码生成器&#xff0c;通过使用GUI的形…
阅读更多...
单词分析与助记之数据建表（以production为例）

单词分析与助记之数据建表（以production为例）

单词分析与助记数据建表&#xff08;以production为例&#xff09;&#xff1a; id&#xff08;流水号&#xff09;&#xff1a;词形&#xff1a;production配图1-标题&#xff1a;略配图1-地址&#xff1a;略配图2-标题&#xff1a;略配图2-地址&#xff1a;略配图3-标题&…
阅读更多...
AI助力决策：告别生活与工作中的纠结，明析抉择引领明智选择

AI助力决策：告别生活与工作中的纠结，明析抉择引领明智选择

在日常生活与工作中&#xff0c;我们时常会面临各种纠结的决策。从选择一份新工作、创业方向&#xff0c;到决定是否要搬家、换车&#xff0c;每一个决策都可能对我们的未来产生深远影响。然而&#xff0c;面对复杂多变的信息和不确定的未来&#xff0c;如何做出明智的选择成为…
阅读更多...
--定位--

--定位--

GPSRTK GPS组成 GPS分为三部分。 空间星座部分&#xff1a;由至少24颗卫星组成&#xff08;目前有30多颗在轨运行&#xff09;&#xff0c;分布在6个中地球轨道上。保证全球任何地方、任何时间至少能接收到4颗以上的卫星信号。每颗卫星不断播发一种包含卫星星历​&#xff0…
阅读更多...
音转文模型对比FunASR与Faster_whisper

音转文模型对比FunASR与Faster_whisper

FunASR简介 FunASR是由阿里巴巴达摩院开源的语音识别工具包&#xff0c;提供包括语音识别&#xff08;ASR&#xff09;、语音活动检测&#xff08;VAD&#xff09;、标点恢复、语言模型、说话人验证、说话人分离及多说话人ASR等多种功能。FunASR工具包支持工业级语音识别模型的…
阅读更多...
uniapp阿里云验证码使用

uniapp阿里云验证码使用

在 UniApp 中使用阿里云验证码插件&#xff08;aliyun-captcha&#xff09;需要完成微信小程序端的插件配置和项目内的组件使用两个主要步骤&#xff0c;以下是详细流程&#xff1a; 一、微信公众平台配置插件&#xff08;必须&#xff09; 获取插件 AppID 阿里云验证码插件的…
阅读更多...
基于开源AI大模型AI智能名片S2B2C商城小程序的情感营销策略研究

基于开源AI大模型AI智能名片S2B2C商城小程序的情感营销策略研究

摘要&#xff1a;本文聚焦于开源AI大模型AI智能名片S2B2C商城小程序这一新兴商业工具&#xff0c;探讨情感在其营销中的核心地位。情感在营销里是需突出表现的关键要素&#xff0c;价值观与极致化生活方式均是对情感的阐释。在开源AI大模型AI智能名片S2B2C商城小程序的背景下&a…
阅读更多...
警惕！你和ChatGPT的对话，可能正在制造分布式妄想

警惕！你和ChatGPT的对话，可能正在制造分布式妄想

2021年圣诞节&#xff0c;19岁的英籍印度裔男子 贾斯旺辛格柴尔 &#xff08;Jaswant Singh Chail&#xff09;带着一把十字弩闯入温莎城堡&#xff0c;声称要 刺杀英国女王 &#xff0c;为英国历史上的暴行复仇。 这场荒谬的刺杀注定以失败告终。被捕后&#xff0c;他自称是一…
阅读更多...
DeepSeek辅助在64位Linux中编译运行32位的asm-xml-1.4程序

DeepSeek辅助在64位Linux中编译运行32位的asm-xml-1.4程序

在网上搜快速xml解析器时找到一个2012年的asm-xml-1.4程序说是比expat快几倍&#xff0c;有点不信&#xff0c;想编译看看。 下载了源代码, 解压缩到/par&#xff0c;其中obj目录下有预编译好的.o文件。 然后运行如下命令编译示例&#xff0c;出错了 cd /par/asm-xml-1.4/exa…
阅读更多...
STM32CubeProgrammer软件安装

STM32CubeProgrammer软件安装

STM32CubeProgrammer软件安装 下载地址 【英文界面】STM32CubeProg | Software - STMicroelectronics 【中文界面】STM32CubeProg | Software - 意法半导体STMicroelectronics 下载 点击获取最新版本下载安装包登录ST账号进行下载当Edge浏览器下载失败时, 换个浏览器下载下…
阅读更多...
数据结构_栈（C语言实现）超详细_Leetcode_20. 有效的括号

数据结构_栈（C语言实现）超详细_Leetcode_20. 有效的括号

目录栈引出栈的定义数据定义栈结构体的定义结构操作- intitStack- freeStack()- empty()- isFull()- top()- pop()- push()- outAll()- 测试完整代码练习题目&#xff1a;Leetcode_20. 有效的括号代码模拟函数调用栈栈引出 栈&#xff0c;在我们日常生活中也非常常见&#xff…
阅读更多...
把装配想象成移动物体的问题

把装配想象成移动物体的问题

移动过后然后匹配两个物体重合的部分做为配合&#xff0c;或者根本就不管&#xff0c;位置对了就行想办法怎么训练ai把加强筋位移过去
阅读更多...
使用 PHP Imagick 扩展实现高质量 PDF 转图片功能

使用 PHP Imagick 扩展实现高质量 PDF 转图片功能

使用 PHP Imagick 扩展实现高质量 PDF 转图片功能 在开发中&#xff0c;经常需要将 PDF 文档转换为图片格式&#xff0c;以便于在线预览、生成缩略图或进行其他图像处理操作。PHP 的 Imagick 扩展提供了强大的图像处理能力&#xff0c;可以轻松实现这一需求。本文将介绍如何使用…
阅读更多...
最新文章

Copyright @ 2022~2023