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];
}
//添加元素到最后一个位置
@Override
public void add(int data) {
//判断数组是否已满
if(isFull()) {
//扩容
grow();
}
arr[arrTrueSize] = data;
arrTrueSize++;
}
//2倍扩容
private void grow() {
arr = Arrays.copyOf(arr,2*ARR_SIZE);
}
//在指定pos位置添加元素
@Override
public 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);
}
}
//判断是否包含某元素
@Override
public boolean contains(int toFind) {
for (int i = 0; i < arrTrueSize; i++) {
if(arr[i] == toFind) {
return true;
}
}
return false;
}
//查找某个元素对应的下标
@Override
public int indexOf(int toFind) {
for (int i = 0; i < arrTrueSize; i++) {
if(arr[i] == toFind) {
return i;
}
}
return -1;
}
//获取pos位置对应的元素
@Override
public 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
@Override
public void set(int pos, int value) {
checkPosOfGetOrSet(pos);
arr[pos] = value;
}
//删除第一次出现的元素
@Override
public 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--;
}
//获取顺序表里面的数据数量
@Override
public int size() {
return arrTrueSize;
}
//清空顺序表
@Override
public void clear() {
arrTrueSize = 0;
}
@Override
public void display() {
for (int i = 0; i < arrTrueSize; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
//判断顺序表是否满了
@Override
public boolean isFull() {
return arrTrueSize == arr.length;
}
//判断顺序表是否为空
@Override
public 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<>();
//处理第一个元素为1
list3.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);
}
//处理最后一个元素为1
list3.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;
}
}
//判断第一个元素是否是key
if(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换为null
if(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;
}
}注意：以上题目是博主写的其中一种解题方法，仅供参考，还有其他方法可以自行去了解。