链表

移除链表元素

删除链表中等于给定值 val 的所有节点。

• 思路 ：思路并不难，只要判断下一个节点的数值是目标数值就将此节点指向下下个节点即可，遇到空链表直接返回，目标值在
  头部将其换到下一个。
• 具体实现：两种方法实现，区别就是在处理头部就是目标值时产生分歧，第一种是判断并交换，第二种是建立虚拟节点，将头节点续在
  其后面，两种方法都要建立节点对象。

!img.png

设计链表

设计

• MyLinkedList obj = new MyLinkedList();
• int param_1 = obj.get(index);
• obj.addAtHead(val);
• obj.addAtTail(val);
• obj.addAtIndex(index,val);
• obj.deleteAtIndex(index);

• 思路：考察链表的增删改，首先要考虑单双节点，然后要创建节点对象，初始化链表需要链表长度为0，然后包含一个头节点，节点值默认为0；
  增加内容在头节点，创建新节点然后让头节点下一个指向它，增加内容在尾节点，同理，增加节点在指定位置，先找到指定位置，然后同样方法插入
  ，当然删除也是一样。

反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

• 思路，其实就是节点内容的转换，转换前准备一个null值节点pre，一个空节点临时存放值，还有一个新节点与头节点内容保持一致
  ，如何做交换，因为是反转，所以先将当前节点的下一个节点值保存在临时值内，然后让当前节点指向pre节点，现在就是c指向p了，
  然后要做的就是将c的值给p,c的下一个值给c,这样完成了反转。
• 具体实现：
  

两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

• 思路：第一种是递归，递归函数里要做的是两两交换返回头节点，拿到这个头节点之后，就可以开始交换了，2指向1，1指向得到的头节点。
• 第二种就是循环，在循环里进行交换的话，需要先定义虚拟节点指向头节点并将其赋予新的节点使其往下前进，所有循环结束后就可返回虚拟节点的下一个节点。

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

• 思路：1.要使用虚拟节点，指向头节点。2.因为是倒数的，所以定义快慢节点，例如要删除倒数第n个，总长是l个，快指针先跑到第n+1的位置，然后快慢指针同时跑
  这样，慢指针就跑到了第l-n-1的位置，而要删除的节点是在l-n的位置，这样就能让慢指针删除要删除的节点了。
• 具体实现：

链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

• 思路： 两种思路：1.取差值后同步进行前进。2.将两链表合并
• 1. 取差值：相交前，链表的长度不同，所以比较两者长度并尾对齐，然后同时前进，比较值是否相同。
• 2. 将链表合并，两链表同时前进，当一个链表的指针走空时，指向另一个链表的头节点继续前进，相当于将两链表首尾相连组成一个大圈，指针从两头开始走，相交后
     的步长一样，相交前的在走第二圈时候已经补齐差距了，所以第二圈能同时到达交点。

环形链表

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

• 思路：快慢指针，快指针比慢指针多走一步，这样进圈之后就一定能相遇，然后通过计算快慢指针的路程，可以得出等式，即为入圈的位置。
  因为是只快了一步，所以不存在跳过的问题，一定会相遇的。

具体实现：