链表的相关知识

什么是链表？

通俗易懂的说链表就是一个通过“链子”来连接起来的数组，而这个在“链子”中是通过指针来进行代表的，通过指针相连的就是数据了，数据和指针就构成了链表中的一个结点，每个结点通过指针指向下一个结点，最后一个结点的指向为空。

链表的分类

单链表：结点之间的指针方向只能是从前往后的，所以查询也只能是从前往后的。

双链表：结点之间的指针方向是既有从前往后的也有从后往前的，所以一个结点有两个指针，即前指针（pre）和后指针（next），所以查询也可双向查询。

循环链表：值得是首尾相连的链表，是单链表的一种特殊情况。

链表的存储

因为链表是通过指针联系在一起的，所以它是随机分配在内存中，但数组不行，数组是在内存中是连续分布的。

链表的优缺点

链表方便删除与增加，因为删除与修改，只需要修改指针的指向即可。 但链表不方便查找，每次只能从头到尾取查找。

与链表不同，数组带有下标，查找某个元素，只需要找下标即可，但数组删除元素与增加元素不放方便，每次移动或删除元素都要移动后面的数。

链表的构造

public class ListNode{
  int val;//结点的值
  ListNode next;//指针指向
  //无参构造方法
  public ListNode(){
  }
  
  //单参构造方法
  public ListNode(int val){
    this.val=val
  }
  
  //全参数构造方法
  public ListNode(int val,ListNode next){
    this.val=val;
    this.next=next;
    
  }
  
  
}

常考算法

推荐题目 ************

获取元素

每次都从头开始遍历，让指针不停的移动，移动到该元素的位置就停下来，然后返回该指针位置的值

移除元素

推荐题目
**************

算法思想： 前 后
1.虚拟头结点法：单独定义一个虚拟头结点，用于处理头结点的删除问题，因为后续元素的删除，都是借助前一元素的指针偏移完成。定义两个指针，初始化时，一个指向虚拟头结点，另外一个指向头结点。然后进入一个循环，用于找到要删除的值，只要找到了要删除的值，就把前指针的下一个指向后指针的下一个指向，如果不等于，就正常把前指针指向后指针，然后就是后指针进行移动，即指向自己的下一个，等待循环结束后，就返回虚拟头结点的下一个，因为要返回的是一个真实结点。
2.不使用虚拟头结点的方法 不用虚拟头结点就需要对头结点先进行判断，判断是否和要删除的值相等，如果是，就要直接把指针向前移动，即该链表头部发生改变。然后其他结点的删除，就直接按照前指针的下一个指向后指针的下一个指向来解决问题

添加元素

首先也是从头开始遍历元素，直到找到插入位置的前一结点，然后把这个插入值的指针的下一个指向前一结点的指针的下一个指向，然后再把前一个结点的下一个指向现在插入值

反转链表

推荐题目 ************

后 前 双指针法：利用两个指针，一前一后，初始化时一个指向为空，然后再定义一个中间指针，用于循环时，反转指针，然后开始循环，只要前指针不为空，就一直循环，循环的内容为，将前指针的下一个赋值给中间指针，然后前指针的下一个指向后指针，最后再更新前后指针的位置，后指针指向前指针，前指针指向前指针的下一个，循环结束后，返回后指针即可，因为循环就代表着，前指针为空了，找到末尾了，而这时后指针指向的就是头结点了

合并链表

分为合并有序链表和合并无序链表

合并有序链表的思路：迭代法
定义一个新的结点，用于存储合并后的链表。定义两个指针，分别执行要合并链表的头结点，然后开始循环（两个指针的指向都不为空），比较两个指针的指向结点的大小，将小的哪些结点加入到合并的链表中，然后移动对应的指针，等到循环结束，还需要判断是否还有剩余的元素，即那个链表不为空，就加入那个链表到合并链表的末尾

题目推荐
合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		
		ListNode merge=new ListNode(-1);

		cur=merge;


		while(l1!=null&&l2!=null){

			if(l1.val>l2.val){

				cur.next=l2;

				l2=l2.next;
			}else{

				cur.next=l1;

				l1=l1.next;

			}


			cur=cur.next;
		}


		if(l1!=null){
			cur.next=l1;
		}else{
			cur.next=l2;
		}


		return merge.next;


}

合并无序链表

两两交换

将链表中的元素，两个一组，进行反转。

推荐题目

迭代法：首先利用虚拟头结点处理头节点的删除问题，虚拟头结点指向头结点， 最后返回的也是虚拟头结点的下一个结点。 定义一个指针，指针指向虚拟头结点。然后进入循环， 循环的条件是指针的下一个指向和下下个指向都不为空。循环的内容为， 首先利用临时指针一存储指针的下一个指向，这样是为了方便后面的指针反转。然后再利用一个临时指针二存储指针的下下下个指向，这样是为了方便每一组数据交换后，方便与下一组的元素产生指针指向关系。 然后就将指针的下一个指向下下个指向，然后再将指针的下下个指向临时指针一，然后再将指针的下下下个指向临时指针二，最后就将指针向前移动两个，最后返回即可。