一、什么是链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
【资料图】
二、链表的分类
2.1单链表
2.2双链表
2.3循环链表
三、代码实现（双链表）
/***@author17122*/publicclassMyLinkedListimplementsIterable{privateintsize;/***改变次数*/privateintmodCount=0;/***头结点指针指向上一个Node的值*/privateNodebeginMarker;/***尾结点指针指向下一个Node的值*/privateNodeendMarker;/***静态内部类**@param*/privatestaticclassNode{publicEdata;//值publicNodeprev;//上一个元素值publicNodenext;//下一个元素值publicNode(Edata,Nodeprev,Nodenext){this.data=data;this.prev=prev;this.next=next;}}/***空构造*/publicMyLinkedList{doClear;}/***清空数组*/privatevoiddoClear{beginMarker=newNode(null,null,null);endMarker=newNode(null,beginMarker,null);beginMarker.next=endMarker;size=0;modCount++;}/***返回大小**@return*/privateintsize{returnsize;}/***判断是否为空**@return*/publicbooleanisEmpty{returnsize==0;}/***添加一个元素**@paramitem*/publicvoidadd(Eitem){add(size,item);}/***向一个位置添加元素**@paramindex*@paramitem*/publicvoidadd(intindex,Eitem){addBefore(getNode(index,0,size),item);}/***获取一个元素**@paramindex*@return*/publicEget(intindex){returngetNode(index).data;}/***获取一个节点**@paramindex*@return*/privateNodegetNode(intindex){returngetNode(index,0,size-1);}/***获取一个元素**@paramindex*@paramlower*@paramupper*@return*/privateNodegetNode(intindex,intlower,intupper){Nodenode;//验证是否合法if(indexupper){thrownewIndexOutOfBoundsException;}//if(indexindex;i--){node=node.prev;}}returnnode;}/***替换值**@paramindex*@paramitem*@return*/publicEset(intindex,Eitem){Nodenode=getNode(index);Edata=node.data;node.data=item;returndata;}/***删除一个元素**@paramindex*@return*/publicEremove(intindex){returnremove(getNode(index));}/***删除一个节点**@paramnode*@return*/privateEremove(Nodenode){node.next.prev=node.prev;node.prev.next=node.next;size--;modCount++;returnnode.data;}/***向头节点添加元素**@paramnode*@paramitem*/privatevoidaddBefore(Nodenode,Eitem){NodenewNode=newNode<>(item,node.prev,node);newNode.prev.next=newNode;node.prev=newNode;size++;modCount++;}@OverridepublicIteratoriterator{returnnewLinkedListIterator;}/***迭代器内部类*/privateclassLinkedListIteratorimplementsIterator{privateNodecurrent=beginMarker.next;privateintexpModCount=modCount;privatebooleanokToRemove=false;@OverridepublicbooleanhasNext{returncurrent!=endMarker;}@OverridepublicEnext{if(modCount!=expModCount){thrownewConcurrentModificationException;}if(!hasNext){thrownewNoSuchElementException;}EnextItem=current.data;current=current.next;okToRemove=true;returnnextItem;}@Overridepublicvoidremove{if(modCount!=expModCount){thrownewConcurrentModificationException;}if(!okToRemove){thrownewNoSuchElementException;}MyLinkedList.this.remove(current.prev);expModCount++;okToRemove=false;}}}复制代码
四、常见算法
4.1合并两个有序链表
问题描述：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。#示例1：输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]#示例2:输入：l1=[],l2=[]输出：[]#示例3：输入：l1=[],l2=[0]输出：[0]#提示：-两个链表的节点数目范围是[0,50]--100<=Node.val<=100-l1和l2均按非递减顺序排列复制代码
题解：
/***合并两个有序链表**@paraml1*@paraml2*@return*/publicstaticListNodemergeTwoLists(ListNodel1,ListNodel2){//如果l1为空就直接输出l2if(l1==null){returnl2;//如果l2为空就直接输出l1}elseif(l2==null){returnl1;//比较l1和l2的值}elseif(l1.val4.2删除链表中重复的元素
问题描述：
题目：存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。返回同样按升序排列的结果链表示例1：输入：head=[1,1,2]输出：[1,2]示例2：输入：head=[1,1,2,3,3]输出：[1,2,3]复制代码
题解：
/***删除链表的重复元素**@paramhead*@return*/publicListNodedeleteDuplicates(ListNodehead){if(head==null){returnnull;}ListNodenode=head;while(node.next!=null){//比较当前元素和下一个元素的值if(node.val==node.next.val){//删除操作node.next=node.next.next;}else{node=node.next;}}returnhead;}复制代码
4.3旋转链表
问题描述：
给你单链表的头节点`head`，请你反转链表，并返回反转后的链表。示例1：输入：head=[1,2,3,4,5]输出：[5,4,3,2,1]示例2：输入：head=[1,2]输出：[2,1]示例3：输入：head=[]输出：[]复制代码
题解：
/***迭代方式**@paramhead*@return*/publicstaticListNodereverseList1(ListNodehead){//定义被反转的新链表ListNodeprev=null;//旧链表ListNodecurr=head;while(curr!=null){//获取旧链表的下一个节点ListNodenext=curr.next;//旧链表的下一个节点指向新链表curr.next=prev;//将旧链表复制到新链表prev=curr;//将旧链表更新为旧链表的下一个节点curr=next;}returnprev;}/***@paramhead*@return*/publicstaticListNodereverseList2(ListNodehead){//递归的终止状态//等于空或只有一个值则返回原链表if(head==null||head.next==null){returnhead;}//进行递归ListNodenewHead=reverseList2(head.next);head.next.next=head;head.next=null;returnnewHead;}复制代码
