链表相关的题，最快的入门方法就是做题的时候画图。标注A的next节点是哪里，单链表的遍历只能是单向的，从头结点到尾结点。
例如：给你一个链表的head头，让你返回最后元素的值
if (head == null) {
return -1;
}
while (head.next != null) {
head = head.next;
}
return head.val;
最近花了大概一个月的时间，将链表的专题刷完了，记录总结一下，题怎么刷比较容易理解，常规套路还有一些题的题解。
1、对于大部分链表的题，我们都需要一个哑结点，就是在头结点之前再创建一个节点并将哑结点的next指向head，这样处理会帮助我们解决边界问题。
2、链表题基本都是对next指针的调整，而不是值本身。
3、对于删除来说就是找前驱，一般会用到快慢双指针。(例如第19题，删除倒数第n个节点)
4、一般来说我们要返回的和过程中处理的是两个引用，因为过程中处理的需要不断的cur = cur.next。而返回时要返回头结点。
5、对于改next指针的时候注意不要路径覆盖，否则会导致死循环。例如(Q24交换链表节点)
6、对于找链表中位数，就是快慢指针，快指针一次移动两次，慢指针一次移动一次。
7、关于环、快慢指针，当fast==slow时证明有环，此时head和slow边移动边比较，相等时就是入环的点。
题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
链接：https://leetcode-cn.com/problems/add-two-numbers
思路：将两个链表当前节点值(当前链表为null，值就是0)相加并加上进位，进位初始化为0，然后创建新的链表对象，新的对象的val为结果%10;然后如果两个链表哪个不为null就往后遍历。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int add = 0;
// cur 作为不断变化的指针
ListNode cur = new ListNode(0);
// res 指向cur后不再变化
ListNode res = cur;
while (l1!=null || l2!=null){
int a1 = l1!=null?l1.val:0;
int a2 = l2!=null?l2.val:0;
int sum = a1+a2+add;
add = sum / 10;
// cur next开始存的是真正的结果
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1!=null){
l1 = l1.next;
}
if (l2!=null){
l2 = l2.next;
}
}
if (add > 0){
cur.next = new ListNode(add);
}
return res.next;
}
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
**进阶：**你能尝试使用一趟扫描实现吗？
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路：哑结点，快慢指针，慢指针指向哑结点，快指针走n步后，快慢一起走。slow.next = slow.next.next移除。
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
// 添加哑结点
ListNode res = new ListNode(0,head);
// slow 和 res指向同一个地址
ListNode slow = res;
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 res.next;
}
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
思路：判断A>B就创建个新的往结果加，最后A，B哪个不为空再加到最后。
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 使用哑结点免去头结点判断代码
ListNode cur = new ListNode(0);
// res是真正从头到尾的链表，cur是控制当前节点动的。
ListNode res = cur;
while (l1!=null && l2!=null){
if (l1.val<=l2.val){
cur.next = new ListNode(l1.val);
l1 = l1.next;
}else {
cur.next = new ListNode(l2.val);
l2 = l2.next;
}
cur = cur.next;
}
if (l1!=null){
cur.next = l1;
}
if (l2!=null){
cur.next = l2;
}
return res.next;
}
题目：给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
思路：归并排序
public ListNode mergeKLists(ListNode[] lists) {
return mergeList(lists,0,lists.length-1);
}
public ListNode mergeList(ListNode[] lists,int head,int tail){
if (head == tail){
return lists[head];
}
if (head > tail){
return null;
}
int mid = (head+tail)/2;
return merge(mergeList(lists,head,mid),mergeList(lists,mid+1,tail));
}
private ListNode merge (ListNode l1,ListNode l2){
ListNode res = new ListNode(-1);
ListNode ans = res;
while (l1!=null && l2!=null){
if (l1.val <= l2.val){
res.next = l1;
l1 = l1.next;
}else {
res.next = l2;
l2 = l2.next;
}
res = res.next;
}
if (l1!=null){
res.next = l1;
}
if (l2!=null){
res.next = l2;
}
return ans.next;
}
题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
思路：利用哑结点，设置next next.next 节点转换，循环就行了，注意的是cur一下跳两个节点
public static ListNode swapPairs(ListNode head) {
ListNode cur = new ListNode(-1);
cur.next = head;
ListNode res = cur;
while (cur.next!=null && cur.next.next!=null){
ListNode tmp1 = cur.next;
ListNode tmp2 = cur.next.next;
tmp1.next = tmp2.next;
tmp2.next = tmp1;
cur.next = tmp2;
cur = cur.next.next;
}
return res.next;
}
题目：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
思路：每k个链表反转，最后拼到一起就行了
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
int len = 0;
List<ListNode> all = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
len++;
if (len == k) {
len = 0;
ListNode next = cur.next;
cur.next = null;
all.add(head);
head = next;
cur = next;
} else {
cur = cur.next;
}
}
return reverse(all, head);
}
public ListNode reverse(List<ListNode> heads, ListNode end) {
ListNode res = new ListNode(-1);
ListNode ans = res;
for (ListNode head : heads) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
res.next = pre;
while (res.next!=null){
res = res.next;
}
}
res.next = end;
return ans.next;
}
题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
思路：将链表连成环，然后移动，然后再将环拆开，
public static ListNode rotateRight(ListNode head, int k) {
// 只有头节点是null的时候需要特殊处理一下
if (head == null) {
return null;
}
ListNode low = head;
ListNode fast = head;
int len = 1;
while (fast!=null){
if (fast.next == null){
// 到链表最后一个节点了，此时将链表连成一个环
fast.next = head;
break;
}
fast = fast.next;
len++;
}
k = k%len;
int loop = len-k;
// len-k代表的是移动方向几次low指向头结点，画图能看出来端倪
while (loop > 0){
low = low.next;
fast = fast.next;
loop--;
}
fast.next=null;
return low;
}
题目：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
思路：找当前的节点和后继节点比较，值一样，while判断后面还有没有一样的，一样的全去掉。如果当前和后继不一样就往后移动一位
public static ListNode deleteDuplicates(ListNode head) {
ListNode res = new ListNode(-1);
res.next = head;
ListNode cur = res;
while (cur.next!=null && cur.next.next!=null){
if (cur.next.val == cur.next.next.val){
int x = cur.next.val;
while (cur.next!=null && x == cur.next.val){
cur.next = cur.next.next;
}
}else {
cur = cur.next;
}
}
return res.next;
}
题目：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
输入：head = [1,1,2]
输出：[1,2]
思路：下一个跟当前相同，就把下一个删了。
public static ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
ListNode res = cur;
while (cur!=null && cur.next!=null){
if (cur.val == cur.next.val){
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return res;
}
题目：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
思路：创建大小两个链表，遍历一遍将大小分开组装，然后大小链表拼起来就行了
public static ListNode partition(ListNode head, int x) {
ListNode cur = head;
ListNode small = new ListNode(-1);
ListNode big = new ListNode(-1);
ListNode res = small;
ListNode tmpBig = big;
while (cur!=null){
if (cur.val<x){
small.next = new ListNode(cur.val);
small = small.next;
}else {
big.next = new ListNode(cur.val);
big = big.next;
}
cur = cur.next;
}
small.next = tmpBig.next;
return res.next;
}
题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
思路：穿针引线把经过的节点放到最前面这样经过[left,right]部分就是反转的了，头插法。先找到pre
public static ListNode reverseBetween(ListNode head, int left, int right) {
ListNode res = new ListNode(-1);
res.next = head;
ListNode pre = res;
int tmpLeft = left;
while (left > 1) {
left--;
pre = pre.next;
}
ListNode cur = pre.next;
int tmp = right - tmpLeft;
ListNode cNext;
while (tmp > 0) {
tmp--;
cNext = cur.next;
cur.next = cNext.next;
cNext.next = pre.next;
pre.next = cNext;
}
return res.next;
}
题目：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
思路：这个就是前序遍历建树就行了。恢复成BST 不断的找中位数，因为链表是有序的，递归时每次把中间的数加为节点进行构造二叉树就可以了
public TreeNode sortedListToBST(ListNode head) {
return createNode(head, null);
}
TreeNode createNode(ListNode head, ListNode tail) {
// 当头==尾时，说明当前节点下面没有子树了。
if (head == tail) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = createNode(head, slow);
root.right = createNode(slow.next, tail);
return root;
}
题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
思路：先复制一份node，A-A’-B-B’-C-C’这样，然后每个节点的random再复制，副本的random等于原random的next；最后再将其拆开。
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
while (cur != null) {
Node node = new Node(cur.val);
node.next = cur.next;
cur.next = node;
cur = node.next;
}
cur = head;
while (cur != null) {
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
Node old = head;
Node newNode = head.next;
Node res = head.next;
while (newNode != null) {
old.next = old.next.next;
newNode.next = newNode.next == null ? null : newNode.next.next;
// 往尾部挂节点
old = old.next;
newNode = newNode.next;
}
return res;
}
题目：给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
思路：快慢指针，如果快慢指针相等代表有环
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
return true;
}
}
return false;
}
题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
思路：快慢指针相等确定有环，然后再用头结点和慢指针一步一步遍历相等的点就是入环的点。
public ListNode detectCycle(ListNode head) {
if (head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
// 有环
ListNode pre = head;
while (pre!=slow){
pre = pre.next;
slow = slow.next;
}
return pre;
}
}
return null;
}
题目：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
思路：快慢指针找到中点，然后将后面的反转，中断前后，最后遍历前后拼接进来。
public void reorderList(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
ListNode reverse = mid.next;
mid.next = null;
ListNode pre = null;
while (reverse!=null){
ListNode next = reverse.next;
reverse.next = pre;
pre = reverse;
reverse = next;
}
while (head!=null && pre!=null){
ListNode h1 = head.next;
ListNode p1 = pre.next;
head.next = pre;
head = h1;
pre.next = head;
pre = p1;
}
}
题目：对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
输入: 4->2->1->3
输出: 1->2->3->4
思路：插入排序，每次从前到后遍历确定插入的位置。
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return null;
}
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode moved = head;
ListNode cur = head.next;
while (cur != null) {
if (moved.val <= cur.val) {
moved = moved.next;
cur = cur.next;
} else {
ListNode prev = pre;
while (prev.next.val <= cur.val){
prev = prev.next;
}
// 将链接上，把cur节点去掉，接上后面的
moved.next = cur.next;
// cur节点移动到前面位置
cur.next = prev.next;
prev.next = cur;
cur = moved.next;
}
}
return pre.next;
}
题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入：head = [4,2,1,3]
输出：[1,2,3,4]
思路：归并排序，注意尾tail作为末位判断
public ListNode sortList(ListNode head) {
return sort(head,null);
}
public ListNode sort(ListNode head,ListNode tail){
// 当头==尾时，说明当前节点下面没有子树了。
if (head == tail){
return head;
}
// 找中点，然后合并，类似构建二叉树
ListNode fast = head;
ListNode slow = head;
while (fast!=tail && fast.next!=tail){
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
ListNode next = mid.next;
mid.next = null;
ListNode left = sort(head, mid);
ListNode right = sort(next, tail);
return merge(left, right);
}
/**
* 合并两个升序链表
* @param l1
* @param l2
*/
public ListNode merge(ListNode l1,ListNode l2){
ListNode res = new ListNode(-1);
ListNode cur = res;
while (l1!=null && l2!=null){
if (l1.val >= l2.val){
cur.next = l2;
l2 = l2.next;
}else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
if (l1!=null){
cur.next = l1;
}
if (l2!=null){
cur.next = l2;
}
return res.next;
}
题目：编写一个程序，找到两个单链表相交的起始节点。
输入：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 个节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：a+b = b+a
/**
* 解题思路：
* a1->a2->c1->c2->c3->b1->b2->b3->c1->c2->c3;
* b1->b2->b3->c1->c2->c3->a1->a2->c1->c2->c3;
* --------------------------------!-----------
* a+b 和 b+a 如果有重合的那么肯定最后的几个元素就是重合的元素、 上面就是！处的c1是重复的
*
* @return
*/
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
思路：遍历，相等就删除
public ListNode removeElements(ListNode head, int val) {
if (head == null){
return null;
}
ListNode res = new ListNode(-1);
res.next = head;
ListNode cur = res;
while (cur!=null && cur.next!=null){
ListNode next = cur.next;
if (next.val == val){
cur.next = next.next;
}else {
cur = cur.next;
}
}
return res.next;
}
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
思路：反转链表
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode cur = head;
ListNode pre = null;
while(cur!=null){
ListNode next = cur.next;
cur.next= pre;
pre = cur;
cur = next;
}
return pre;
}
请判断一个链表是否为回文链表。
输入: 1->2->2->1
输出: true
思路：先找中点，然后反转后面，然后遍历对比都相等，则是回文。
public static boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
return result;
}
private static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private static ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
// next和next.next能保证偶数链表中点出现在前面 1-2-3-4 2的位置 而 fast fast.next的方式中点会出现在3的位置需要额外判断
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
思路：当前节点值是下一个节点的值，然后把下一个节点删除，这样就能达到效果了。
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
题目：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
思路：双节点，奇数节点和偶数节点。穿针引线。
public ListNode oddEvenList(ListNode head) {
if (head == null){
return null;
}
ListNode odd = head;
ListNode res = odd;
ListNode even = head.next;
ListNode evenTmp = even;
while (even !=null && even.next!=null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenTmp;
return res;
}
题目：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：
输入的多级列表如下图所示：
1---2---NULL
|
3---NULL
思路：这个就是广度优先遍历，使用Deque 队列。但是有个小坑，就是是一个双链表，要把结果的child置空，prev指向前驱。
public Node flatten(Node head) {
if (head == null){
return null;
}
Deque<Node> stack = new ArrayDeque<>();
Node res = new Node(-1);
Node ans = res;
stack.push(head);
while (!stack.isEmpty()){
Node pop = stack.pop();
if (pop.next!=null){
stack.push(pop.next);
}
if (pop.child!=null){
stack.push(pop.child);
}
// 指前后节点，child置空
pop.next = null;
pop.child = null;
res.next = pop;
pop.prev = res;
res = res.next;
}
ans = ans.next;
ans.prev = null;
return ans;
}
题目：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
思路：这个需要遍历到尾，然后再加，再加就像两数相加一样。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
while (l1!=null){
stack1.push(l1.val);
l1 = l1.next;
}
while (l2!=null){
stack2.push(l2.val);
l2 = l2.next;
}
ListNode cur = null;
int add = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || add !=0){
int a = stack1.isEmpty()?0:stack1.poll();
int b = stack2.isEmpty()?0:stack2.poll();
int sum = a+b+add;
add = sum / 10;
ListNode node = new ListNode(sum%10);
node.next = cur;
cur = node;
}
return cur;
}
题目：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
思路，类中定义一个链表，维护链表的数据
class MyLinkedList {
ListNode head;
int size;
public MyLinkedList() {
head = new ListNode(-1);
size = 0;
}
public int get(int index) {
if (index <0 || index>=size){
return -1;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.next.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if (index < 0 ){
index = 0;
}
if (index > size){
return;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
ListNode node = new ListNode(val);
node.next = cur.next;
cur.next = node;
size++;
}
public void deleteAtIndex(int index) {
if (index<0 || index>=size){
return;
}
ListNode cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = cur.next.next;
size--;
}
}
题目：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：先分每个段几个元素然后从头往后遍历，将对应的元素放到返回数组里。
public static ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] res = new ListNode[k];
if (root == null){
return res;
}
int[] arr = new int[k];
ListNode loop = root;
int len = 0;
while (loop!=null){
len++;
loop = loop.next;
}
// 分配每个段几个元素
for (int i = 0; i < len; i++) {
arr[i%k]++;
}
ListNode cur = root;
for (int i = 0; i < arr.length; i++) {
int tmp = arr[i];
ListNode nowNode = new ListNode(-1);
nowNode.next = cur;
ListNode tmpNode = nowNode;
while (cur!=null && tmp>0){
tmp--;
cur = cur.next;
tmpNode = tmpNode.next;
}
tmpNode.next = null;
res[i] = nowNode.next;
}
return res;
}
题目：给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。
同时给定列表 G，该列表是上述链表中整型值的一个子集。
返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
思路：当前节点在G中出现且next节点在G中没出现就是组件的次数，G中所有的元素能构成多少个head中相连的子链表？
public int numComponents(ListNode head, int[] G) {
if (head == null){
return 0;
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < G.length; i++) {
map.put(G[i],null);
}
int res = 0;
ListNode cur = head;
while (cur!=null){
if (map.containsKey(cur.val) && (cur.next==null||!map.containsKey(cur.next.val))){
res++;
}
cur = cur.next;
}
return res;
}
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
输入：[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.
思路：快慢双指针找中点。
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;
}
题目：给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
思路：求解下一个更大的值，这种就是用单调栈。1下一个比1大的是7，5下一个比它大的是9如果没有比自己大的就是0
public int[] nextLargerNodes(ListNode head) {
if (head == null){
return new int[]{0};
}
List<Integer> list = new ArrayList<>();
while (head!=null){
list.add(head.val);
head = head.next;
}
int[] res = new int[list.size()];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < list.size(); i++) {
// 4,1,7,3,5
while (!stack.isEmpty() && list.get(stack.peek())<list.get(i)){
// 栈不为空，栈顶小于当前值。 栈里是 4，1 当前是7 那么1出栈(1在数组中的索引是1)，设置1的索引对应的下一个最大值为7。
// 继续循环，栈里是4，当前是7 那么4出栈(4在数组中的索引是0)，设置0的索引对应的下一个最大值为7然后栈空或者下一个栈顶值小于7打破循环
// 如果没有更大值就是默认值的0，如果数组是 9,1,7,3,5 那么9肯定不会出栈，9的索引0也不会被赋值
Integer index = stack.pop();
res[index] = list.get(i);
}
stack.push(i);
}
return res;
}
new Stack
for（遍历处理数组）{
while（栈非空 && 达到预期条件）{ // 一般预期条件是栈顶 < 当前位置的值
出栈并处理，保存到结果集
}
入栈（栈中保存数组的索引）
}
while(栈非空){ // 如果这道题就不需要这步了。因为不存在是0，0就是int的默认值
出栈处理剩余栈内元素
}
题目：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
思路：需要两遍遍历，第一次遍历构建一个map，map的key是遍历过程中的sum和，value为遍历过程中的list. 第二次遍历，如果get(sum)能取到，就证明cur和get取出来的列表之间的和是0；那么cur.next = get.next;
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
Map<Integer, ListNode> map = new HashMap<>();
// 首次遍历建立 节点处链表和<->节点 哈希表
// 若同一和出现多次会覆盖，即记录该sum出现的最后一次节点
int sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
map.put(sum, d);
}
// 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
sum = 0;
for (ListNode d = dummy; d != null; d = d.next) {
sum += d.val;
d.next = map.get(sum).next;
}
return dummy.next;
}
题目：给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
思路：先反转，然后遍历链表，过程中记录要乘的基数。 按照2进制进行乘 加 就行了
public int getDecimalValue(ListNode head) {
if (head == null) {
return 0;
}
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
int loop = 1;
int sum = 0;
while (pre != null) {
sum += pre.val * loop;
pre = pre.next;
loop *= 2;
}
return sum;
}
题目：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。
思路：前序遍历树，然后head作为每个树节点的参照物。
public boolean isSubPath(ListNode head, TreeNode root) {
if (head == null){
return true;
}
if (root == null){
return false;
}
return sub(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
}
private boolean sub(ListNode head, TreeNode root){
if (head == null){
return true;
}
if (root == null){
return false;
}
if (head.val != root.val){
return false;
}
return sub(head.next,root.left) || sub(head.next,root.right);
}
题目：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
思路：删list1 然后记录断点，list2遍历到尾，将其拼接上就行
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode res = new ListNode(0);
res.next = list1;
ListNode cur = res;
for (int i = 1; i < a; i++) {
cur = cur.next;
}
ListNode pre = cur;
int move = b-a;
while (move >=0 && cur != null){
move--;
cur = cur.next;
}
pre.next = list2;
ListNode cur2 = list2;
while (cur2!=null && cur2.next!=null){
cur2 = cur2.next;
}
cur2.next = cur.next;
return res.next;
}
题目：给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]
思路：找到对应节点，然后换值、
public ListNode swapNodes(ListNode head, int k) {
if (head == null){
return head;
}
ListNode slow = head;
ListNode fast = head;
for (int i = 1; i < k; i++) {
fast = fast.next;
}
ListNode node1 = fast;
while (fast!=null && fast.next!=null){
fast = fast.next;
slow = slow.next;
}
int tmp = node1.val;
node1.val = slow.val;
slow.val = tmp;
return head;
}
以上：剩下的剑指offer和面试题都是重复的题了、