1. (LeetCode-21)合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
思路: 双指针或者递归，既然是有序链表排序，那么我们可以制定一个l1指向第一个链表 l2指向第二个链表，再建立一个结果链表和一个指针p，然后比较两个链表的大小，比较一个数值，就挂在p的后面，因此无外乎几种情况1. l1为null，直接返回l2；2.l2为null，直接返回l1，3.链表有值进行比较 3.1.l1先完 直接将l2剩余的挂在p后面 l2先完，将l1挂在p后面，如图所示
代码实现如下:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null ) return list2;
if(list2 == null ) return list1;
ListNode head = new ListNode(0); // 创建一个空Node
ListNode p = head; // 指针p指向头节点
while (list1 != null && list2 != null ) {
if(list1.val <= list2.val ) {
p.next = list1;
list1 = list1.next;
}else {
p.next = list2;
list2 = list2.next;
}
p = p.next;
}
if (list1 != null ) {
p.next = list1;
}
if(list2 != null ) {
p.next = list2;
}
return head.next; // 返回链表
}
}递归的思路就是每移掉一个接口，就是相当于两个新的有序链表重新排序，递归结束条件就是某一个链表为null，可以自行实现 ，其算法复杂度也是O(m+n)
2. (LeetCode-83)删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。示例 1：
输入：head = [1,1,2] 输出：[1,2]示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
思路: 指针，将当前节点的val与next节点的val进行比较，若相等，则当前节点的next直接跳到next.next。代码实现
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null ) {
return head;
}
ListNode cur = head;
while (cur.next != null ) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return head;
}
}3. (LeetCode-141)环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环
思路： 快慢指针，快指针一次挪两下，慢指针一次挪一下，如果是个环的话，快慢指针就一定会相遇。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null ) return false;
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null ) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {
return true;
}
}
return false;
}
}4. (LeetCode-142)环形链表II
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
思路: 同样快慢指针，那么快慢指针相遇的地方肯定是环中的某个地方，然后此时把慢指针放到头节点，与快指针同时移动同样的步长1,这样，再次相遇的地方就是环开始的地方，代码如下:
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null ) return null;
ListNode fast = head;
ListNode slow = head;
boolean loopExists = false;
while(fast.next != null && fast.next.next != null ) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow){ //在环中相遇了表示有环
loopExists = true;
break;
}
}
if(loopExists) {
ListNode slowStr = head;
while (slowStr != fast ) {
slowStr = slowStr.next;
fast = fast.next;
}
return slowStr;
}
return null;
}
}5.(LeetCode-160) 相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点
headA和headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：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 。进阶：你能否设计一个时间复杂度
O(m + n)、仅用O(1)内存的解决方案？
思路: 双指针，A B指针同时遍历指向headA和headB,当遍历完一遍之后，重新换一次指向，这样就可以消除a b之间的链表的长度差，当再次相遇的时候，就是两个链表的交叉点了，代码如下:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null ) return null;
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB ) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}6.(LeetCode-206)反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]
思路: 要进行链表的反转，可以假定一个preNode,然后链表向后遍历，每遍历一个节点，它的next指向指向preNode,preNode向后移动一下，代码如下:
class Solution {
public ListNode reverseList(ListNode head) {
ListNode preNode = null;
ListNode cur = head;
while (cur != null ) {
ListNode next = cur.next;
cur.next = preNode;
preNode = cur;
cur = next;
}
return preNode;
}
}7.(LeetCode-234)回文链表
给你一个单链表的头节点
head，请你判断该链表是否为回文链表
。如果是，返回true；否则，返回false。示例 1：
输入：head = [1,2,2,1] 输出：true示例 2：
输入：head = [1,2] 输出：false提示：
- 链表中节点数目在范围
[1, 105]内0 <= Node.val <= 9进阶：你能否用
O(n)时间复杂度和O(1)空间复杂度解决此题？
思路: 快慢指针，因为回文链表是对称型的，因此快指针移动到末尾的时候，慢节点会移动到链表的中间，此时将慢节点之后的链表进行反转 然后依次与原链表比较，直到慢链表结束，如果有值不相等，则一定不是回文链表
代码如下:
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null ) return false;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null ) {
slow = slow.next;
}
slow = converse(slow);
fast = head;
while (slow != null ) {
if(fast.val != slow.val ) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
private ListNode converse(ListNode head) {
ListNode preNode = null;
ListNode cur = head;
while (cur != null ) {
ListNode next = cur.next;
cur.next = preNode;
preNode = cur;
cur = next;
}
return preNode;
}
}8.(LeetCode-876)链表的中间结点
给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
思路： 快慢指针，因为快指针是慢指针步幅的两倍， 因此快指针到达末尾的时候，慢指针刚好到达中间值，代码如下:
class Solution {
public ListNode middleNode(ListNode head) {
if (head == null ) return null;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}9. 总结
力扣的链表专题，主要就是快慢指针的灵活运用，要学会合理的构建指针，构建空链表，以存储不同的链表节点，灵活运用链表的指向关系即可。
