1、leetcode136.删除链表的结点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 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.
① 双指针求解
public ListNode deleteNode(ListNode head, int val) {//初始化一个虚拟节点ListNode dummy = new ListNode(0);//让虚拟节点指向头结点dummy.next = head;ListNode cur = head;ListNode pre = dummy;while (cur != null) {if (cur.val == val) {//如果找到要删除的结点，直接把他删除pre.next = cur.next;break;}//如果没找到，pre指针和cur指针都同时往后移一步pre = cur;cur = cur.next;}//最后返回虚拟节点的下一个结点即可return dummy.next;
}- 删除一个结点，先获取该结点的上一个结点
② 递归
public ListNode deleteNode(ListNode head,int val){if(head == null) return head;if(head.var == val) return head.next;head.next = deleteNode(head.next,val);return head;
}2、leetcode24.两两交换链表中的结点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
① 非递归
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0,head);ListNode temp = dummy;while(temp.next != null && temp.next.next != null){ListNode start = temp.next;ListNode end = temp.next.next;temp.next = end;start.next = end.next;end.next = start;temp = start;}return dummy.next;}
}② 递归（没看懂！）
class Solution {public ListNode swapPairs(ListNode head){ if(head == null || head.next == null){return head;}ListNode next = head.next;head.next = swapPairs(next.next);next.next = head;return next;}
}3、leetcode160.相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点
headA和headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 ：
输入：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 。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0- 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度
O(m + n)、仅用O(1)内存的解决方案？
① 双指针
解题思路：设【第一个公共点】为 node，【链表 headA】的结点数量为 a，【链表 headB】的结点数量为 b，【两链表的公共尾部】的节点数量为 c，则有：
- 头节点 headA 到 node 前，共有 a - c 个节点；
- 头节点 headB 到 node 前，共有 b - c 个节点；
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA，headB，做如下操作：
- 指针 A 先遍历完链表 headA，再开始遍历链表 headB，当走到 node 时，共走步数为：
a + (b - c)
- 指针 B 先遍历完链表 headB，再开始遍历链表 headA，当走到 node 时，共走步数为：
b + (a - c）
- 如下式所示，此时指针 A ，B 重合，并有两种情况：
a + (b - c) = b + (a - c)
- 若两链表有公共尾部（即 c > 0）：指针 A , B 同时指向【第一个公共节点】 node
- 若两链表无公共尾部（即 c = 0）：指针 A , B 同时指向 null
因此返回 A 即可。
public class Solution {public ListNode getIntersectionNode(ListNode headA,ListNode headB){if (headA == null || headB == null) {return null;}ListNode A = headA, B = headB;while(A != B){A = A != null ? A.next : headB;;B = B != null ? B.next : headA;}return A;}
}② 哈希集合
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
- 如果当前节点不在哈希集合中，则继续遍历下一个节点
- 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有结点都在两个链表的相交部分，因此在链表 headB 中遍历的第一个在哈希集合中的节点就是两个量表相交的节点，返回该节点。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}
