【本节目标】
1. ArrayList 的缺陷
2. 链表
3. 链表相关 oj题目
一. ArrayList的缺陷
上节课已经熟悉了ArrayList 的使用，并且进行了简单模拟实现。通过源码知道， ArrayList 底层使用数组来存储元素：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ...
// 默认容量是10
private static final int DEFAULT_CAPACITY = 10;
//...
// 数组：用来存储元素
transient Object[] elementData; // non-private to simplify nested class access
// 有效元素个数
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// ...
} 由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。
二. 链表
1 链表的概念及结构
链表是一种物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
单向------双向
循环------ 非循环
带头------ 不带头
（1） 单向或者双向
（2） 带头或者不带头
（3） 循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种 :
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
- 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2 链表的实现
1、无头单向非循环链表实现
链表的基本表示：
static class ListNode{
public int val;
public ListNode next;
public ListNode(int data){
this.val=data;
}
}
public ListNode head;//链表的头对应的方法：
public interface IList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void clear() ;
public void display();
}
实现对应的方法:
(1)display
public void display() {
ListNode cur=head;//不能改变头的引用
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
}(2)size
public int size() {
int len=0;
ListNode cur=head;
while (cur!=null){
len++;
cur=cur.next;
}
return len;
}(3)contains
public boolean contains(int key) {
ListNode cur=new ListNode(key);
while(cur!=null){
if(cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}(4)addFirst/头插
public void addFirst(int data) {
ListNode listNode=new ListNode(data);//该节点是新的头节点
listNode.next=head;
head=listNode;
}(5)addFirst/尾插
public void addLast(int data) {
ListNode listNode=new ListNode(data);
if(head==null){
head=listNode;
return;
}
ListNode cur=head;
while(cur.next!=null){
cur=cur.next;
}
cur.next=listNode;
}(6)addIndex/任意位置插
public void addIndex(int index, int data) {
int len=size();
if (index<0||index>len){
new IndexOutOfBoundary("index输入有误");
return;
}
if(index==0){
addFirst(data);
return;
}
if(index==len){
addLast(data);
return;
}
int curLen=0;
ListNode cur=head;
ListNode listNode=new ListNode(data);
while(curLen<index-1){
curLen++;
cur=cur.next;
}
listNode.next=cur.next;
cur.next=listNode;
}(7)remove
public void remove(int key) {
if(head==null){//链表为空
return;
}
if(head.val==key){//删除的位置在头节点
head=head.next;
return;
}
ListNode pre=findPreNodeOfKey(key);
if(pre!=null){
ListNode del=pre.next;//找到需要删除的节点
pre.next=del.next;
}
}
private ListNode findPreNodeOfKey(int key){
ListNode cur=head;
while(cur.next!=null){//最后一个节点也已经判断过了
if (cur.next.val==key){
return cur;
}
cur=cur.next;
}
return null;
}(8)removeAllKey
public void removeAllKey(int key) {
if(head==null){
return;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(cur.val==key){
prev.next=cur.next;
cur= cur.next;
}else {
prev=prev.next;
cur= cur.next;
}
}
//把前面的除头节点之外的都删完之后删除头节点
if (head.val==key){
head=head.next;
}
}(9)clear
public void clear() {
ListNode cur=head;
while (cur!=null){
ListNode curN=cur.next;
cur.next=null;//基本数据类型的val不需要回收
cur=curN;
}
}三.链表相关题目
1. 删除链表中等于给定值 val 的所有节点。
/**
* 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 data){
if(head==null){
return head;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(cur.val==data){
prev.next=cur.next;
cur=cur.next;
}else{
prev=prev.next;
cur=cur.next;
}
}
if(head.val==data){
head=head.next;
}
return head;
}
}
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;
}
ListNode cur=head.next;
head.next=null;
while(cur!=null){
ListNode curN=cur.next;
cur.next=head;
head=cur;
cur=curN;
}
return head;
}
}3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
/**
* 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;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}4. 输入一个链表，输出该链表中倒数第 k 个结点。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
int count=0;
ListNode f=pHead;
while(f!=null){
count++;
f=f.next;
}
if(k>count||k<=0){
return null;
}
if(pHead==null){
return pHead;
}
// write code here
ListNode prev=pHead;
ListNode cur=pHead;
while((k-1)!=0){
cur=cur.next;
k--;
}
while(cur!=null&&cur.next!=null){
prev=prev.next;
cur=cur.next;
}
return prev;
}
}经过重新调整，除了计算出有多少元素，防止多删除之外，可以在快指针走的时候就进行判断，走太多就会超过限制，那么就会走到空指针出，也可以判断
while((k-1)!=0){
cur=cur.next;
k--;
if(cur==null){
return null;
}
}5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* 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 cur1=list1;
ListNode cur2=list2;
ListNode newHead=new ListNode();
ListNode tmp=newHead;
if(cur1==null&&cur2==null){
return null;
}
while(cur1!=null&&cur2!=null){
if(cur1.val<=cur2.val){
tmp.next=cur1;
cur1=cur1.next;
tmp=tmp.next;
}else{
tmp.next=cur2;
cur2=cur2.next;
tmp=tmp.next;
}
}
if(cur1!=null){
tmp.next=cur1;
cur1=cur1.next;
tmp=tmp.next;
}
if(cur2!=null){
tmp.next=cur2;
cur2=cur2.next;
tmp=tmp.next;
}
return newHead.next;
}
}6. 编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前 。
- 利用两个链表，一个存放小于x的值，一个存放大于x的值
- 要注意的是最后的判断条件，可能不存在小于x的，则直接返回第二个链表；且如果第二个链表不为空，链表结尾要置空，防止越界。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode list1start=null;
ListNode list1end=null;
ListNode list2start=null;
ListNode list2end=null;
while(pHead!=null){
if(pHead.val<x){
if(list1start==null){
list1start=list1end=pHead;
}else{
list1end.next=pHead;
list1end=list1end.next;
}
}else{
if(list2start==null){
list2start=list2end=pHead;
}else{
list2end.next=pHead;
list2end=list2end.next;
}
}
pHead=pHead.next;
}
if(list1start==null){
return list2start;
}
list1end.next=list2start;
if(list2start!=null){
list2end.next=null;
}
return list1start;
}
}7. 链表的回文结构。
使用快慢指针，找到中间节点，将中间节点之后的结点进行反转。然后分别向中间比较。
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) {
// write code here
if(head == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow 指向的位置 就是中间节点
//2.进行翻转
ListNode cur = slow.next;
while (cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
//3.判断回文
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 pl=headA;
ListNode ps=headB;
int len1=0;
int len2=0;
while(pl!=null){
pl=pl.next;
len1++;
}
while(ps!=null){
ps=ps.next;
len2++;
}
pl=headA;
ps=headB;
int k=len1-len2;
if(k<0){
pl=headB;
ps=headA;
k=0-k;
}
while(k!=0){
pl=pl.next;
k--;
}
while(pl!=ps){
pl=pl.next;
ps=ps.next;
}
//若两个链表不相交
if(pl==null){
return null;
}
return pl;
}
}9. 给定一个链表，判断链表中是否有环。
/**
* 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(fast==slow){
return true;
}
}
return false;
}
}【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】
- 为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
- 快指针一次走3步，走4步，...n步行吗？
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
起点到入口点的距离和相遇点到入口点的距离相等
此时slow从开头处开始走，fast从相遇点开始走，以相同的速度运动，相遇时则为相交点
/**
* 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){
fast=fast.next.next;
slow=slow.next;
if(slow==fast){
break;
}
}
if(fast==null||fast.next==null){
return null;
}
slow=head;
while(slow!=fast){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}结论
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针 都是每次均走一步，最终肯定会在入口点的位置相遇 。
证明
