LinkedList与链表

一、链表

链表相关练习题

二、LikedList

1、构造方法

2、常用方法

3、LinkedList的遍历

4、ArrayList与LinkedList的区别

一、链表

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的

链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的结点一般是从堆上申请出来的
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续也可能不连续

链表的结构多种多样，就单向/双向、有无头结点、是否循环3种情况组合起来就有8种链表结构，我们重点掌握两种：

无头单向非循环链表：结构简单，一般不会单独用于存储数据，而是作为其他数据结构的子结构，如哈希桶、图的邻接表等
无头双向非循环链表：Java的集合框架中LinkedList底层实现

链表相关练习题

删除链表中等于给定值val的所有结点
反转单链表（头插法）
给定单链表头结点返回中间结点，若有2个则返回第2个（快慢指针）
输出单链表倒数第K个结点（差值）

public ListNode FindKthToTail(int k){if(k<0 || k>size) return null;ListNode slow=head;ListNode fast=head;for(int i=0;i<k-1;i++){fast=fast.next;if(fast==null) return null;}while(fast!=null){fast=fast.next;slow=slow.next;}return slow;
}

5、合并两个有序链表（串珠子）

class Solution {public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode newHead=new ListNode();ListNode tmpHead=newHead;while(headA!=null && headB!=null){if(headA.val>headB.val){tmpHead.next=headB;headB=headB.next;}else{tmpHead.next=headA;headA=headA.next;}tmpHead=tmpHead.next;}if(headA!=null){tmpHead.next=headA;}if(headB!=null){tmpHead.next=headB;}return newHead.next;}
}

6、以给定值为基准，所有小于此值的排在大于或等于此值之前（分割合并）

public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode bs=null;ListNode be=null;ListNode as=null;ListNode ae=null;ListNode cur=pHead;while(cur!=null){if(cur.val<x){if(bs==null) {bs=be=cur;}else{be.next=cur;be=be.next;}}else{if(as==null) {as=ae=cur;}else{ae.next=cur;ae=ae.next;}}cur=cur.next;}if(bs==null)return as;be.next=as;if(as!=null){ae.next=null;}return bs;}
}

7、判断是否为回文结构（快慢指针、翻转链表）

 public boolean chkPalindrome(ListNode head) {//1、找到中间链表结点ListNode slow=head;ListNode fast=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}//2、翻转中间结点以后的链表ListNode cur=slow.next;while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//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、输入两个链表找出它们第一个公共结点（双指针、差值）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//1、求2个链表长度的差值int lenA=0,lenB=0;ListNode pL=headA;ListNode pS=headB;while(pL!=null){lenA++;pL=pL.next;}while(pS!=null){lenB++;pS=pS.next;}int len=lenA-lenB;pL=headA;pS=headB;if(len<0){len=lenB-lenA;pL=headB;pS=headA;}//2、让pL先走len步，后两个链表同时走while(len>0){pL=pL.next;len--;}while(pL!=null && pS!=null){if(pS==pL){return pL;}pL=pL.next;pS=pS.next;}return null;}

9、判断给定单链表中是否有环

public boolean hasCycle(ListNode head) {if(head==null) return false;ListNode fast=head,slow=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){return true;}}return false;     
}

10、返回给定链表开始入环的第一个结点（快慢指针法）

两指针相遇时路程fast=L+nC+(C-y)；slow=L+C-y
则L+nC+(C-y)=2L+2C-2y
L=nC+C-y-2C+2y=(n-1)C+y
即头节点到入环点的距离=绕几圈再走到相遇点的距离
那我们让a指针头节点开始走，b指针从相遇点开始走饶了好几圈之后再走y距离就能和a指针相遇，相遇点就为入环点

public ListNode detectCycle(ListNode head) {if(head==null) return null;ListNode fast=head,slow=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow)//二者相遇break;}//是因为无环才跳出循环if(fast==null || fast.next==null)//因循环条件不满足而跳出循环return null;//有环，因为快慢指针相遇才跳出循环，此时就让一指针从head出发，另一指针从相遇点出发，两者相遇点即为入环点fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;
}

二、LikedList

LinkedList的底层是无头双向非循环链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的结点中，然后通过引用将结点连接起来，因此在任意位置插入或删除元素时不需要搬运元素，效率比较高，时间复杂度为O(1)

1、构造方法

LinkedList()	无参构造
LinkedList(Collection<? extends E> c)	使用其他容器中元素构造List

2、常用方法

方法	解释
boolean add (E e)	尾插 e
void add (int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
E remove(int index)	删除 index 位置元素
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
boolean remove(Object o)	删除遇到的第一个 o
List<E> subList(int fromIndex, int toIndex)	截取部分 list
void clear()	清空

3、LinkedList的遍历

public static void main(String[] args) {LinkedList<Integer> list=new LinkedList<>();for (int i = 1; i < 6; i++) {list.add(i);//尾插}System.out.println(list.get(0));//1、foreach遍历for (int e: list)System.out.print(e+" ");System.out.println();//2、迭代器正向遍历ListIterator<Integer> it=list.listIterator();while (it.hasNext())System.out.print(it.next()+" ");System.out.println();//3、迭代器反向遍历ListIterator<Integer> rit=list.listIterator(list.size());while (rit.hasPrevious())System.out.print(rit.previous()+" ");
}

4、ArrayList与LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，物理上不一定
随机访问	支持：O(1)	不支持：O(N)
头插	需要搬运元素，效率低：O(N)	只需要修改引用的方向：O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁