一.插入节点
1.在链表中插入最大公约数
给你一个链表的头 head，每个节点包含一个整数值
在相邻节点之间，请你插入一个新的节点，节点值为这两个相邻节点值得 最大公约数
请你返回插入之后得链表
两个数得 最大公约数 是可以被两个数字整除得最大正整数
示例：
输入：head = [18, 6, 10, 3]
输出：[18, 6, 6, 2, 10, 1, 3]
class Solution {public ListNode insertGreatestCommonDivisors(ListNode head) {ListNode cur = head;while (cur.next != null) {//插入节点int gcd = gcd(cur.val, cur.next.val);//先记录下来原先得nextListNode temp = cur.next;//新插入节点 以及新节点next指向原nextcur.next = new ListNode(gcd, temp);//当前变为原先next 或者当前next.nextcur = temp;}return head;}//公约数 两个数 相互取模，为0了，另一个树就是最大公约数private int gcd(int a, int b) {while (a != 0) {//不为0 两个数就交换int temp = a;a = b % a; //另一个数模自己 比自己小就是交换 否则就算出来了b = temp; //两数交换}return b;}}二.反转链表(整个链表反转)
1.反转链表
给你一个单链表的头节点 head，请你反转链表，并返回反转后的链表
示例：
输入：head = [1, 2, 3, 4, 5]
输出：[5, ,4 ,3 ,2 ,1]
class Solution {public ListNode reverseList(ListNode head) {//可以新建一个链表，然后原链表遍历将数据存在集合或者数组中//然后倒叙遍历集合数组进行新链表的组件//优化时间和空间 就在原链表上进行反转操作//声明一个pre节点 pre节点必须为null 因为反转过来//pre节点就是尾节点的下一个节点 肯定是null //一个cur节点ListNode pre = null, cur = head;while (cur != null) {//先保存cur的下一个节点引用 这样就将链表分为两段了 一个是左边已经反转了//一个是右边原链表ListNode temp = cur.next;//然后将cur.next指向pre节点进行反转cur.next = pre;//pre指向cur进行往后遍历pre = cur;//然后cur也往后进行遍历cur = temp;}return pre;}
}2.反转链表II(链表中间部分反转)
这段题解是参考了灵神的思路，感兴趣的同学可以去学习一下灵神的题解：
【基础算法精讲 06】
给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right，请你反转从位置 left
到位置 right 的链表节点，返回反转后的链表。
示例：
输入：head = [1, 2, 3, 4, 5]，left = 2，right = 4， index从1开始
输出：[1, 4, 3, ,2, 5]
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {/**链表中间反转 思路：找到left-1和right+1 其实就是反转的start和end然后left-1.next指向right，反转right-left之间的元素反转完之后right+1的前一个节点应该就是原先的left节点然后left.next指向right+1即可所以参考上一题链表反转 声明两个指针 一个指向pre 一个指向cur*///头节点也有可能需要反转 ListNode dummy = new ListNode(0, head);ListNode start = dummy;//找到left-1节点 索引从1开始for (int i = 0; i < left - 1; i++) {start = start.next;}//然后从下一个节点作为cur节点开始反转一直到right+1ListNode pre = null, cur = start.next;for (int i = 0; i < right - left + 1; i++) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//这个时候已经反转结束了 而且cur已经是right+1节点了//而pre节点就是right节点//所以start.next是原链表节点2 然后next指向cur节点//start新的next指向pre节点start.next.next = cur;start.next = pre;return head;}
}三.前后指针
1.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点
示例：
输入：head = [1, 2 ,3, 4, 5 ]，n = 2
输出：[1, 2, 3, 5]，倒数第2个节点是4，删除节点4
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {/**双指针第一个指针指向head，然后走n步这时候再声明一个指针指向head，然后两个前后指针同步走这个时候前一个指针和后一个指针始终会相差 n 当前一个指针走到链表的尾节点了，这个时候第二个指针所在的位置就是倒数n+1的位置了删除第二个指针的next即可*/ListNode dummy = new ListNode(0, head), first = dummy;for (int i = 0; i < n && first.next != null; i++) {first = first.next;}ListNode second = dummy;while (first.next != null) {first = first.next;second = second.next;}second.next = second.next.next;return dummy.next;}
}2.旋转链表
给你一个链表的头节点 head，旋转链表，将链表的每个节点向右移动 k 个位置
示例：
输入：head = [1, 2, 3, 4, 5]，k = 2
输出：[4, 5, 1, 2, 3]
class Solution {public ListNode rotateRight(ListNode head, int k) {/**先计算链表的长度，然后用k%len计算旋转点如果结果=0 则表示不用旋转然后将原链表反转接下来遍历反转的链表找到旋转点然后从旋转点分割链表为两段接下来分别对两段链表进行反转最后合并两条链表即可当然 还有更暴力的做法：就是用数组来存储链表数据然后旋转数组 然后组建新的链表*/if (head == null) return head; int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}int index = k % len;if (index == 0) return head;//开始反转ListNode pre = reverse(head);//然后计算分割点ListNode newHead = pre, pre1 = null;while (index-- > 0) {ListNode next = newHead.next;newHead.next = pre1;pre1 = newHead;newHead = next;}//pre1已经成为了新的head newHead后面开始第二段链表反转ListNode pre2 = reverse(newHead);//第一段的尾部next指向pre2ListNode cur1 = pre1;while (cur1.next != null) {cur1 = cur1.next;}cur1.next = pre2;//返回pre1return pre1;}private ListNode reverse(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}
}3.交换链表中的节点
给你链表的头节点 head 和一个整数 k
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头部
链表从 1开始索引
示例：
输入：head = [1, 2, 3, 4, 5]，k = 2
输出：[1, 4, 3, 2, 5]，正数第2个是2，倒数第2个是4，两者交换
class Solution {public ListNode swapNodes(ListNode head, int k) {/**确定整数第k个node然后找到倒数第k个node 用双指针一个先走k 然后同步走，最后后指针位置就是倒数k+1*/ListNode dummy = new ListNode(0, head), f = dummy;while (k-- > 0 && f.next != null) {f = f.next;}ListNode s = dummy, left = f;while (f.next != null) {f = f.next;s = s.next;}int temp = left.val;left.val = s.next.val;s.next.val = temp;return dummy.next;}
}四.快慢指针
1.链表的中间节点
给你单链表的头节点 head，请你找出并返回链表的中间节点
如果有两个中间节点，则返回第二个中间节点
示例：
输入：head = [1, 2, 3, 4, 5]
输出：[3, 4, 5]，3是中间节点
示例：head = [1, 2, 3, 4, 5, 6]
输出：[4, 5, 6]，中间节点是3，4，返回第二个中间节点4
class Solution {public ListNode middleNode(ListNode head) {/**快慢指针，第一个指针走2步 第二个指针走1步当第一个指针走到尾节点的时候，第二个指针肯定是指向中间节点的*/ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;}return s;}
}2.删除链表的中间节点
给你一个链表的头节点 head，删除链表的中间节点，并返回修改后的链表的头节点head
长度为 n 的链表的中间节点是从头数起第 [n / 2] 个节点(下标从0开始)，其中 [x] 表示小于
或等于 x 的最大整数
对于 n = 1, 2, 3, 4, 5的情况，中间节点的下标分别是0, 1, 1, 2, 2(其实就是第二个中间节点)
示例：
输入：head = [1, 3, 4, 7, 1, 2, 6]
输出：[1, 3, 4, 1, ,2, 6]，中间节点是7
输入：head = [1, 2, 3, 4]
输出：[1, 2, 4]
class Solution {public ListNode deleteMiddle(ListNode head) {/**因为下标是从0开始的，所以中间节点如果是偶数个的话就是第二个这题主要考的还是删除节点和找中间节点因为删除的是中间节点，所以本质是复制next节点给当前要删除的节点，然后next指向next.next*///有可能要删除本身 ListNode dummy = new ListNode(0, head);//注意 如果是要删除第二个中间节点//快指针从head开始//如果是删除第一个 那么就从dummy开始ListNode f = head, s = dummy;while (f != null && f.next != null) {f = f.next.next;s = s.next;}//删除s下一节点节点s.next = s.next.next;return dummy.next;}
}3.回文链表
给你一个单链表的头节点 head，请你判断该链表是否为 会问链表，如果是，返回true
否则，返回false
示例：
输入：head = [1, 2, 2, 1]
输出：true
class Solution {public boolean isPalindrome(ListNode head) {/**由于是单链表 没办法直接从head访问tail所以先找到中间节点，然后从中间节点开始一直到最后反转然后一个从反转之和的head开始遍历，一个从原链表开始遍历如果两者一直到反转链表遍历完都相等则是回文串既学习找中间节点 又可以学习链表反转*/ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;}//从s节点开始反转ListNode pre = null, cur = s;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//开始遍历 最好是不要破坏原headListNode cur2 = head;while (pre != null) {if (cur2.val != pre.val) return false;cur2 = cur2.next;pre = pre.next;}return true;}
}4.链表最大孪生和
在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1的 i，第 i 个节点
(下标从0开始)的孪生节点为第 (n - 1 -i)个节点
比方说：n = 4，那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。
这是长度为 n = 4的链表中所有的孪生节点
孪生和 定义为一个节点和它孪生节点两者值之和
给你一个长度为偶数的链表的头节点 head，请你返回链表的最大孪生和
示例：
输入：head = [5, 4, 2, 1]
输出：6，
解释：5 + 1 = 6，4 + 2 = 6，这是上述链表所有的孪生和，最大值就是6
class Solution {public int pairSum(ListNode head) {/**想一想，孪生节点怎么找？因为链表长度是偶数，那么是不是可以用中间节点来表示孪生节点呢？找到中间节点，然后从中间节点开始断开反转(反转任意一边的链表)这样就生成两条链表，这两条链表对应的顺序节点就是对方的孪生节点*/ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;}//从s开始反转ListNode pre = null, cur = s;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//计算孪生和最大值int max = Integer.MIN_VALUE;ListNode head2 = head;while (pre != null && head2 != null) {max = Math.max(pre.val + head2.val, max);pre = pre.next;head2 = head2.next;}return max;}
}5.重排链表
给定一个单链表 L 的头节点 head，单链表 L 表示为：
L0 -> L1 -> ...... -> L N - 1 -> LN
请你将其重新排序后变为
L0 -> LN ->L1 -> L N - 1 -> L2 -> L N - 2 ->......
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
示例：
输入：head = [1, 2 , 3, 4]
输出：[1, 4, 2, 3]
class Solution {public void reorderList(ListNode head) {/**首先按照题目来找规律明显就是和找孪生节点类似 原节点-孪生节点-原节点-孪生节点如果是奇数个，那么尾节点就是中间节点所以思路是：先找到中间节点然后反转后半部分链表，然后两个链表同步遍历进行组装成新的链表，因为是需要实际的节点交换 而并不是只是改变节点的值所以需要next指向真实的孪生节点*///先找中间节点ListNode mid = middleNode(head);//在反转后半段ListNode head2 = reverseList(mid);//进行交替插入//注意 这里要进行next判断 因为反转玩只会两个链表是//head=[1,2,3] head2=[4,3]都包含3 所以中间节点在原链表while (head2.next != null) {//先暂存两个头节点的next 否则以交换就找不到原先的next了ListNode next = head.next, next2 = head2.next;//原链表next指向新链表head 1->4head.next = head2;//新链表next指向原链表next 1->4->2head2.next = next;//两个链表往后遍历head = next;head2 = next2;}}private ListNode reverseList(ListNode mid) {ListNode pre = null, cur = mid;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}private ListNode middleNode(ListNode head) {ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;}return s;}
}6.环形链表
给你一个链表的头节点 head，判断链表中是否有环
如果链表存在环，则返回true，否则返回false
示例：
输入：
输出：true
public class Solution {public boolean hasCycle(ListNode head) {/**判断一个链表是否有环，用快慢指针因为如果存在环，那么快指针肯定会在循环N次后追上慢指针因为一个指针是走2步，一个是走1步，有环，肯定会相交*/ListNode f = head, s = head;while (f != null && f.next != null) {//如果有环肯定会一直循环 直到两指针相交//否则没环肯定会退出f = f.next.next;s = s.next;if (f == s) return true;}return false;}
}7.环形链表II
给定一个链表的头节点 head，返回链表开始入环的第一个节点，如果链表无环，返回null
不允许修改链表，索引从0开始
示例：
图解：
解释：
- f = 2s（快指针走2步，慢指针走1步）
- f = s + n*b （相遇时，f多走了n圈）
所以s = n * b，那么从head节点走到入环点就是需要a+nb，这个时候s已经走了nb，
那么s再走a就到了入环点了，所以这个时候从head和s一起走，相遇就是走了a
就是入环点。
public class Solution {public ListNode detectCycle(ListNode head) {/**这题就是判断环形的变种先判断是否有环，有环的情况下，在声明一个指针从head，然后和当前快慢指针任意一个同步走当俩指针相交时，就是入环的第一个节点*/ListNode f = head, s = head;while (f != null && f.next != null) {f = f.next.next;s = s.next;if (f == s) {ListNode cur = head;while (cur != s) {cur = cur.next;s = s.next;}return cur;}}return null;}
}五.双指针
1.奇偶链表
给定单链表的头节点 head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，
然后返回重新排序的列表。
第一个节点的所以被认为是奇数，第二个节点的索引被认为是偶数，以此类推
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致
你必须在0(1)的额外空间复杂度和0(n)的时间复杂度下解决这个问题
示例：
输入：head = [1, 2, 3, 4, 5]
输出：[1, 3, 5, 2, 4]
class Solution {public ListNode oddEvenList(ListNode head) {/**就是将奇数节点按先后顺序从头节点开始排好序然后接下来就是偶数节点按先后顺序思路：定义两个指针，既然说明了第一个节点被认为是奇数，第二个是偶数那么一个指针指向第一个节点，一个指针指向第二个节点然后每个指针都走两步，这样第一个指针都是奇数节点第二个指针都是偶数节点然后最后一个奇数节点next指向第一个偶数节点*/ if (head == null || head.next == null) return head;//先保存第一个节点的引用，防止丢失ListNode odd = head, oddHead = head;ListNode even = head.next, evenHead = head.next;while (even != null && even.next != null) {//先暂存在自身的next 防止丢失ListNode oddNext = odd.next.next, evenNext = even.next.next;//奇数next和偶数next都指向自身的next.nextodd.next = oddNext;even.next = evenNext;//然后本身都往后移动到next.nextodd = oddNext;even = evenNext;}//odd指向evenHeadodd.next = evenHead;return oddHead;}
}2.相交链表
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点
如果两个链表不存在相交节点，返回null
图示两个链表在节点 c1 开始相交
图解：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {/**这题可以参考快慢指针 找环形链表的入环点这相交链表是一样的，可以把两条链表想象成一个环形链表 相交点就是入环点思路：定义两个指针a和b分别遍历链表a和b，当a到了尾部，将a指向b的head同理，当b到了尾部，将b指向a的head，然后当a==b的时候，就是相交点原理同环形链表 */ListNode curA = headA, curB = headB;//为什么边界问题是 curA == curB//因为两条链表不相交的话 最终都会等于null 所以返回null就等于没有相交点while (curA != curB) {curA = curA == null ? headB : curA.next;curB = curB == null ? headA : curB.next;}return curA;}
}六.合并链表
1.合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回
新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：head1 = [1, 2, 4]，head2 = [1, 3, 4]
输出：[1, 1, 2, 3, 4, 4]
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {/**可以新增一个链表，也可以在原链表上进行修改本质是链表的遍历和节点插入*/ListNode head = new ListNode(0);ListNode cur = head;//要考虑的两个问题：1长2短 1短2长 所以边界问题要定好while (list1 != null && list2 != null) {//谁小先拼接谁if (list1.val < list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}//最后看谁没遍历完 就拼接剩下的cur.next = list1 == null ? list2 : list1;return head.next;}
}