本文涉及的leetcode对应的题
leetcode第876题链表的中间节点
leetcode第160题相交链表
leetcode第237题删除链表当前节点
leetcode剑指offer18题删除链表中的某个节点
leetcode第19题删除链表的倒数第N个节点
leetcode第141题环形链表 I
leetcode第142题环形链表 II
leetcode第1290题二进制链表转整数
leetcode第206题反转一个单链表
leetcode第24题两两交换链表中的节点
leetcode第21题合并两个有序链表
leetcode第25题K个一组翻转链表

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }@Overridepublic String toString() {return "ListNode [val=" + val + ", next=" + next + "]";}
}

1.给定数组构建链表

public static void main(String[] args) {int[] nums = new int[] {1,2,3,4,5};ListNode node = new ListNode(-1);ListNode temp = node;for (int i = 0; i < nums.length; i++) {temp.next = new ListNode(nums[i]);temp = temp.next;}System.out.println(node.next);
}

ListNode [val=1, next=ListNode [val=2, next=ListNode [val=3, next=ListNode [val=4, next=ListNode [val=5, next=null]]]]]

2.链表的中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。

1.1.借用外部空间

解题要素：知道中间节点的位置
遍历链表，将遍历后的链表存储到list集合中，然后获取list的中间元素。

public static ListNode middleNode(ListNode head) {if(head ==null) {return null;}List<ListNode> list = new ArrayList<>();int index = 0;while (head != null) {list.add(head);index ++;head = head.next;}return list.get(index/2);
}

当然也可以不用list，可以定义一个指针，第一次遍历求长度，然后在遍历一半的长度。

public static ListNode middleNode2(ListNode head) {int index = 0;ListNode temp = head;while (temp != null) {index ++;temp = temp.next;}int flag = 0;temp = head;while (flag < index / 2) {flag ++;temp = temp.next;}return temp;
}

1.2.双指针：快慢双指针

设置两个指针，慢指针一次走一步，快指针一次走两步，当快指针走到末尾了（null），则慢指针刚好走到中间位置。

public ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}

3.相交链表

编写一个程序，找到两个单链表相交的起始节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

3.1.暴力双循环

通过示例1和示例2我们不难得出，此题不能根据值是否相同来判断。因此我们需要判断的是地址，即判断class是不是同一个，而不能判断class的val属性。第一个循环链表A，然后逐个和链表B中的各节点对比地址。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tempA = headA;ListNode tempB = headB;while (tempA != null) {while (tempB != null) {if(tempA == tempB) {return tempA;}tempB = tempB.next;}tempA = tempA.next;//重新初始化tempBtempB = headB;}return null;}

3.2.Hash优化循环

针对暴力双循环，我们可以使用hashSet或者hashMap来优化掉一层循环

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> hashHeadA = new HashSet<>();while (headA != null){hashHeadA.add(headA);headA = headA.next;}while (headB != null){if (hashHeadA.contains(headB)){return headB;}headB = headB.next;}return null;}
}

3.3.双指针：链表拼接

起点不同，构造相同长度让它们相遇，这样A走的路程就是A表+B表，B走的路程就是B表+A表，当AB和BA相遇的时候，就是相交节点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode tempA = headA,tempB = headB;while (tempA != tempB) {tempA = tempA == null ? headB : tempA.next;tempB = tempB == null ? headA : tempB.next;}return tempA;}

4.删除链表当前节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点 。
现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
提示：
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

4.1.偷梁换柱

仔细看完题后，感觉很纳闷，入参不应该是两个么？一个是链表，一个是需要删除的节点，但是实际要求我们实现的是，删除传入的节点，也就是说，我们压根不知道链表是什么样子，也就是node节点之前的节点是啥。
可能我们理解的是在：A->B->C->D链表中，删除节点C，因此我们常规删除就是将A指向C，就能删除B了，但是此题给的是B->C->D，此时需要我们把B删了，我们发现A找不到了，这里可以用C覆盖B的方式求解。既然找不到A，我们就把C完全覆盖给B，这样不管A在哪里，都会指向C。此时B就被删除了。

public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;
}

5.删除链表中的某个节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

5.1.比较值删除

和上题不同的是，这里我们是用值来判断删除，也就是根据值更改指向。

	public ListNode deleteNode(ListNode head, int val) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode temp = dummy;while(temp.next != null){if(temp.next.val == val){temp.next = temp.next.next;return dummy.next;}temp = temp.next;}return dummy.next;}

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

6.1.两遍循环

第一次遍历找出总长度，第二次遍历找出需要删除的节点。
考虑到某些特殊情况，如链表为空，或者只有一个节点。我们可以做一个哑结点。

	 public ListNode removeNthFromEnd(ListNode head, int n) {//哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部ListNode dummy = new ListNode(0);dummy.next = head;int length  = 0;ListNode temp = head;while (temp != null) {length++;temp = temp.next;}length = length - n;temp = dummy;while (length > 0) {length--;temp = temp.next;}temp.next = temp.next.next;return dummy.next;}

6.1.双指针：先后指针

我们让快指针先走n步，然后快慢指针一次走一步，当快指针走到末尾时，慢指针就走到了需要删除的节点处。

 	public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode fast = dummy;ListNode slow = dummy;for (int i = 0; i <= n; i++) {fast = fast.next;}while (fast != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}

7.环形链表 I

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

7.1.hash优化暴力双循环

采用暴力的话，我们的复杂度是O（n*n），我们可以循环链表节点之后，将这个节点存储到hash中，如果，我们遍历到某个元素时，在hash中，找到了这个节点，说明这个链表是环形链表，因为我们回到了我们之前遍历的节点。
注意：这里使用的是内存地址，而不是具体的值。

 	public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while (head != null) {if(set.contains(head)) {return true;} else  {set.add(head);}head = head.next;}return false;}

7.2.双指针：快慢指针（Floyd ）

Floyd 判圈算法（又称龟兔赛跑算法）,假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇
定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

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

8.环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？

8.1.hash优化暴力双循环

与环形链表I类似，如果我们用一个 Set 保存已经访问过的节点，我们可以遍历整个列表并返回第一个出现重复的节点。不同的是，我们这里返回的是第一个环节点，而不是true/false。

 	public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while (head != null) {if (set.contains(head)) {return head;}else {set.add(head);}head = head.next;}return null;}

7.2.双指针：快慢指针（Floyd ）

基于环形链表 I，我们先判定是不是环形链表，在环形链表的基础上，我们在去寻找环形入口在哪儿。

如上图所示：我们假设快指针只饶了一个环，快指针和慢指针就能相遇。
那么快指针走的长度必然是慢指针的两倍
如上图所示：
2(a + b) = a + b + c + b
a = c
最终我们得出a=c，因此我们只需要快慢指针，此时一步一步的走，走到最后一步就是环状入口。
假设快指针已经走了几个环，同理
a + n ( b + c ) + b = a + ( n + 1 ) b + nc
a = c + ( n − 1 )( b + c )
从相遇点到入环点的距离加上 n-1圈的环长，恰好等于从链表头部到入环点的距离。
因此还是快慢指针一步一步的往下走，慢指针走到头的位置就是环入口。

	public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (true) {if (fast == null || fast.next == null) {return null;}fast = fast.next.next;slow = slow.next;if(fast == slow) {break;}}slow = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return slow;}

9.二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
输入：head = [0]
输出：0
示例 3：
输入：head = [1]
输出：1
示例 4：
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：
输入：head = [0,0]
输出：0
提示：
链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

9.1.API转换Integer.valueOf

遍历此链表，然后拼接一个字符串，然后将此字符串用API转成二进制。

 	public int getDecimalValue(ListNode head) {StringBuffer buff = new StringBuffer();while (head != null) {buff.append(head.val);head= head.next;}return Integer.valueOf(buff.toString(), 2);}

9.2.位移运算

左移代表乘，左移一位代表乘2,左移两位代表乘4，依次递增。例如12<<1=24;12<<2=48
右移代表除，右移一位代表除2,右移两位代表除4，依次递增。例如12>>1=6;12>>2=3
先来看看二进制怎么转10进制
1011 = 12^3 + 02^2 + 12^1 +12^0，我们对这个表达式进行公因式的提炼，如下红花圈部分刚好就是我们的二进制数1011。

不难发现如下规律，每次计算都是 2 * a + b，其中b为对应权位上的二进制数，
因此得出公式： sum(n) = 2 * sum(n-1) + b

    public int getDecimalValue(ListNode head) {int sum = 0;while (head != null) {//乘2相当于左移1位，除2相当于右移1位//sum = sum * 2 + head.val;sum <<= 1;sum = sum + head.val;head = head.next;}return sum;}

10.反转一个单链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

10.1.借用外部空间

使用list集合存储所有的节点，然后按照list集合的反序循环，创建节点，此时创建的链表就是反转后的链表

	public ListNode reverseList(ListNode head) {List<Integer> list = new ArrayList<>();ListNode headTemp = new ListNode(0);while (head != null) {list.add(head.val);head = head.next;}ListNode temp = headTemp;for (int i = list.size() - 1; i>=0; i--) {temp.next = new ListNode(list.get(i));temp = temp.next;}return headTemp.next;}

10.2.迭代法

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。

    public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode temp = curr.next;curr.next = prev;prev =curr;curr = temp;}return prev;}

11.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]

11.1.递归：使用递归模板

使用递归求解此问题时，我们先来看一个递归模板
当我们实现一个递归函数的时候，我们需要先抽取出如下三个模块
1、递归终结条件；
2、处理当前递归层的逻辑；
3、进入下一层递归；

	public void/Object recursion(Object obj1,Object obj2) {//递归终止条件if(obj1 != obj2) {return;//return new Object();}//当前层递归处理逻辑//进入下一层递归recursion(obj1, obj2);//Object obj = recursion(obj1, obj2);}

我们举个例子：
例如链表是123456，我们需要反转成214365
21、43、65我们可以看做三次操作来完成，对于21操作，我们是将12变成21，然后将1和下一次操作返回的节点进行链接。
根据上述模板，我们来看：
1、递归终止条件：两个互换的节点，任意一个为null，即当前节点为null，或者next为null；

public ListNode swapPairs(ListNode head) {//1、递归终止条件if(node == null || node.next == null) {return node;}//2、当前层递归处理逻辑//3、进入下一层递归swapPairs(head);
}

2、当前递归层逻辑处理：将原本的node1指向node2，变成node2指向node1，然后node1指向下一次递归返回的节点（下次递归返回43）；

public ListNode swapPairs(ListNode head) {//1、递归终止条件if(node == null || node.next == null) {return node;}//2、当前层递归处理逻辑：取出node2ListNode node2 = node.next;//3、进入下一层递归//2、当前层递归处理逻辑：将node指向下一次递归返回的节点node.next = swapPairs(node.next.next);//2、当前层递归处理逻辑：将node2指向node1node2.next = node;
}

11.2.迭代法：单一到循环

对于链表1234，反转后是2143，必然会执行两次操作，那么我们可以先别考虑多个操作时，只考虑第一次操作，
将1234变成2134

因此我们代码实现就是如下所示：实现效果为1234变成2134

	public static ListNode swapPairs2(ListNode head) {ListNode dummy = new ListNode(-1);dummy.next = head;//哨兵节点：存储指向头节点的指针ListNode prevNode = dummy;//需要交换的节点 node1 和node2ListNode node1 = head;ListNode node2 = head.next;//交换node1和node2prevNode.next = node2;node1.next = node2.next;node2.next = node1;return dummy.next;}

在完成21交换后，因此我们接下来还需要执行34的交换，而执行34的交换，和12的交换是一样的操作，也就是需要重复进行12的操作，唯一区别就是操作的元素不是12 而是34，哨兵节点也不再-1，而是1。

	public static ListNode swapPairs2(ListNode head) {ListNode dummy = new ListNode(-1);dummy.next = head;//哨兵节点：存储指向头节点的指针ListNode prevNode = dummy;while (head != null && head.next != null) {//需要交换的节点ListNode node1 = head;ListNode node2 = head.next;//交换prevNode.next = node2;node1.next = node2.next;node2.next = node1;prevNode = node1;head = node1.next;}return dummy.next;}

12.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

12.1.借用外部空间：创建有序链表

依次循环两个链表，获取到链表中的元素后，将元素排序好以后，然后根据创建好的元素创建链表。

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {List<Integer> list = new ArrayList<>();while (l1 != null) {list.add(l1.val);l1 = l1.next;}while (l2 != null) {list.add(l2.val);l2 = l2.next;}if(list.isEmpty()) {return null;}Collections.sort(list);ListNode newlistNode = new ListNode(list.get(0));ListNode temp = newlistNode;for (int i = 1; i < list.size(); i++) {temp.next = new ListNode(list.get(i));temp = temp.next;}return newlistNode;} 

12.2.递归：单一到循环

在上一题中，两两交换链表的节点，我们使用递归模板来解决，其实我们可以在换另一种思维来解决。从单一体到循环体来思考。
假设有两个链表，两个链表最多只有一个节点，这时我们来合并这两个链表。
node1 : [2]；node2：[1] 合并后 node2[1,2]，并考虑node1和node2可能为空的时候

	public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) {					return l2;			//node1为空，所以直接返回node2} else if (l2 == null) {return l1;			//node2为空，所以直接返回node1} else if (l1.val < l2.val) {l1.next = l2;		//node1小于node2,所以node1指向node2return l1;} else {l2.next = l1;		//node2小于node1,所以node12指向node1return l2;}}

因此执行上述代码后，我们就可以针对单一节点的链表进行合并了。当我们实现了单个节点的链表合并排序后，其实，接下里的重复过程，就是将小的节点指向下一次递归返回的节点。

	public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) {					return l2;			//node1为空，所以直接返回node2} else if (l2 == null) {return l1;			//node2为空，所以直接返回node1} else if (l1.val < l2.val) {//l1.next = l2;		//node1小于node2,所以node1指向node2l1.next = mergeTwoLists(l1.next,l2);return l1;} else {//l2.next = l1;		//node2小于node1,所以node12指向node1l2.next = mergeTwoLists(l1,l2.next);return l2;}}

12.3.迭代

   	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}prev.next = l1 == null ? l2 : l1;return prehead.next;}

13.K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

综上：在链表相关的算法中，我们最为直接的就是采取暴力的方式直接遍历链表，然后做判断。
遍历链表的时候一般有如下两种方式：
递归，迭代
在某些情况下，我们可以借用外部资源，如hash，List，利用这些数据结构来解决链表的问题，或者可以设置两个指针做遍历。