链表
链表可以分为单链表和双向链表。 单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。
单链表 ： A -> B -> C -> null.
public class SinglyListNode {
int val;
SinglyListNode next;
SinglyListNode(int x) { val = x; }
}
操作单链表无法像数组一样通过下标索引查找。需要遍历链表查找，时间复杂度是O(N). 插入和删除操作，就是改变指针的指向，时间复杂度为O(1)。
设计链表
class MyLinkedList {Node head; int size;
/** Initialize your data structure here. */ public MyLinkedList() { size = 0; }
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ public int get(int index) { if(index < 0 || index >= size) { return -1; }
int i = 0; Node ptr = head; while(i < index) { ptr = ptr.next; i++; } return ptr.val; }
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ public void addAtHead(int val) { Node node = new Node(val); if(head != null) { node.next = head; } head = node; size++; }
/** Append a node of value val to the last element of the linked list. */ public void addAtTail(int val) { addAtIndex(size, val); }
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ public void addAtIndex(int index, int val) { if(index > size) { return; }
if(index == 0) { addAtHead(val); return; }
Node ptr = head; int i = 0; while(i < index - 1) { ptr = ptr.next; i++; } Node node = new Node(val); Node next = ptr.next; ptr.next = node; node.next = next; size++; }
/** Delete the index-th node in the linked list, if the index is valid. */ public void deleteAtIndex(int index) { if(index < 0 || index >= size) { return; }
if(index == 0) { Node next = head.next; head.next = null; head = next; size--; return; }
int i = 0; Node ptr = head; while(i < index - 1) { ptr = ptr.next; i++; } Node nextTwo = ptr.next.next; ptr.next.next = null; ptr.next = nextTwo; size--; }
static class Node{ int val; Node next;
public Node(int val) { this.val = val; } } }
1. 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/jbex5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
快慢双指针模板：
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // move slow pointer one step each time
fast = fast.next.next; // move fast pointer two steps each time
if (slow == fast) {
return true; // change this logic to fit specific problem
}
}
return false; // change return value to fit specific problem
方法一： 如果题目没有要求空间复杂度，可遍历链表把节点加入HashSet，如果存在循环则第二次加入时hashset就已经存在了，就可以判断存在循环。
public class Solution { public boolean hasCycle(ListNode head) { Setreturn false; } } 方法二：快慢双指针来解该问题。 在链表中使用两个速度不同的指针时会出现以下两种情况：
-
如果没有环，快指针将停在链表的末尾。 -
如果有环，快指针最终将与慢指针相遇。
一个安全的选择是每次移动慢指针一步，移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
public class Solution { public boolean hasCycle(ListNode head) { ListNode slowNode = head; ListNode fastNode = head; ListNode meetNode = null;while(fastNode != null && fastNode.next != null) { slowNode = slowNode.next; fastNode = fastNode.next.next;
if(slowNode == fastNode) { meetNode = fastNode; break; } } if(meetNode != null) { return true; } else { return false; } } }
2. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/jjhf6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路： 和上题一样，可以通过HashSet判断环及环的开始节点。 这里要求空间复杂度为O(1), 所以使用快慢双指针。
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slowNode = head; ListNode fastNode = head; ListNode meetNode = null;
while(fastNode != null && fastNode.next != null) { slowNode = slowNode.next; fastNode = fastNode.next.next;
if(slowNode == fastNode) { meetNode = fastNode; break; } } if(meetNode == null) { return null; } //相遇后，从相遇点和head开始移动的步数一致可到达环的开始点。 while(head != null){ if(head == meetNode) { return meetNode; } head = head.next; meetNode = meetNode.next;
} return null; } }
3. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/jf1cc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路：通过快慢指针，快指针先行n部，接着快慢指针同时走。知道快指针到最后，把慢指针指向下下个节点完成删除。
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fastNode = head; ListNode dummy = new ListNode(0); ListNode slowNode = dummy; dummy.next = head;
while(n-- > 0) { fastNode = fastNode.next; }
while(fastNode != null) { fastNode = fastNode.next; slowNode = slowNode.next; }
ListNode temp = slowNode.next.next; slowNode.next.next = null; slowNode.next = temp;
return dummy.next; } }
4. 反转链表
4.1 反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULLclass Solution { public ListNode reverseList(ListNode head) { ListNode ptr = null;
方法一：
while(head != null) { ListNode temp = head.next; head.next = ptr; ptr = head; head = temp; }
return ptr; } } 方法二；递归调用 public ListNode reverseList(ListNode head) { if(head == null || head.next == null) { return head; }
ListNode tail = head.next; ListNode res = reverseList(head.next); head.next = tail.next; tail.next = head;
return res;
}
4.2 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
使用递归，反转链表
class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(); dummy.next = head; ListNode parent = dummy; int count = right - left + 1; while(left > 1) { parent = parent.next; left--; } ListNode res = traverseN(parent.next, count); parent.next = res;return dummy.next; }
public ListNode traverseN(ListNode node, int n) { if(n == 1) return node; ListNode tail = node.next; ListNode res = traverseN(node.next, n-1); node.next = tail.next; tail.next = node; return res; } } 4.3 两两交换链表
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head;ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head;
return newHead; } } 4.4 K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(); dummy.next = head; ListNode ptr = dummy; ListNode q = ptr.next;while((ptr.next = reverse(q, k)) != q) { ptr = q; q = ptr.next; }
return dummy.next; }
public ListNode reverse(ListNode node, int k) { ListNode p = node; int count = k;
while(--count > 0 && p != null) { p = p.next; } if(p == null) { return node; } return reverseK(node, k); }
public ListNode reverseK(ListNode node, int k) { if(k == 1){ return node; }
ListNode tail = node.next; ListNode res = reverseK(node.next, k - 1); node.next = tail.next; tail.next = node;
return res; } }
5. 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
解题思路：可以通过哨兵节点去解决它，哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode ptr = dummy; while(head != null){ if(head.val == val) { ptr.next = head.next; } else{ ptr = head; } head = head.next; } return dummy.next; } }
6. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/fe0kj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路：链表分成奇偶链表。最后把偶链表拼接到奇链表。
class Solution { public ListNode oddEvenList(ListNode head) { if(head == null) { return head; } ListNode oddList = head; ListNode evenHead = head.next; ListNode evenList = evenHead;while(evenList != null && evenList.next != null) { oddList.next = evenList.next; oddList = oddList.next; evenList.next = oddList.next; evenList = evenList.next; }
oddList.next = evenHead; return head; } }
7.回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/fov6t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法一: 解题思路：遍历head节点，存入ArrayList. 用双指针从两头往中间收缩查找是否有不同的字符。
class Solution { public boolean isPalindrome(ListNode head) { if(head == null) { return true; } Listwhile(head != null) { nums.add(head.val); head = head.next; }
int size = nums.size(); for(int i = 0; i < size; i++) { if(!nums.get(i).equals(nums.get(size - 1))) { return false; } size--; } return true; } } 方法二： 要用O(1) 空间，那就不能借助ArrayList。 在原有的链表上就行操作。通过快慢指针找到中间的节点, 这里会涉及到奇数和偶数个节点，所以要注意中间节点的查找方式。在中间节点的后半部分进行链表反转后和前半部分比较。 class Solution { public boolean isPalindrome(ListNode head) { if(head == null) { return true; } ListNode midNode = findMidNode(head); ListNode secHalfList = reverseList(midNode.next); ListNode firstHaldList = head; boolean result = true; while(secHalfList != null) { if(firstHaldList.val != secHalfList.val) { result = false; break; } firstHaldList = firstHaldList.next; secHalfList = secHalfList.next; }
return result; }
private ListNode findMidNode(ListNode head) { ListNode slowNode = head; ListNode fastNode = head;
while(fastNode.next != null && fastNode.next.next != null) { fastNode = fastNode.next.next; slowNode = slowNode.next; } return slowNode; }
private ListNode reverseList(ListNode head) { ListNode parent = null; while(head != null) { ListNode temp = head.next; head.next = parent; parent = head; head = temp; }
return parent; } }
82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
while(pre.next != null) { if(pre.next.next != null && pre.next.val == pre.next.next.val) { ListNode q = pre.next.next; while(q != null && q.val == pre.next.val) { q = q.next; } pre.next = q; } else { pre = pre.next; } }
return dummy.next; } }
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode p = head;
while(p != null && p.next != null) {
if(p.val == p.next.val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
}
}
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/f00a2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路：把链表的尾部和头部相连，做一个循环链表。在从中间断连。从断链的下个节点作为新的头结点。
class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null) { return head; } ListNode ptr = head; ListNode result = head; int size = 1; while(ptr.next != null) { size++; ptr = ptr.next; } ptr.next = head;k = k % size;
int moveStep = size - k - 1; while(moveStep > 0) { moveStep--; result = result.next; }
head = result.next; result.next = null;
return head; } }
双向链表： null <-A<->B<->C-> null
定义：双向链表中每个节点维护了一个前向和后置的节点链接。
class DoublyListNode {
int val;
DoublyListNode next, prev;
DoublyListNode(int x) {val = x;}
}
1. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/fv6w7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2. 扁平化多级双向链表
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：
输入的多级列表如下图所示：
扁平化后的链表如下图：
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：
输入的多级列表如下图所示：
1---2---NULL
|
3---NULL
示例 3：
输入：head = []
输出：[]
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/fw8v5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解题思路： 把图竖起来，就是一颗二叉树。把child看成左子树，next看成右子树。用前序遍历解此题。
/* // Definition for a Node. class Node { public int val; public Node prev; public Node next; public Node child; }; */class Solution { public Node flatten(Node head) { if(head == null) { return null; } Node dummy = new Node(0, null, head, null);
flattenList(dummy, head); dummy.next.prev = null; return dummy.next; }
private Node flattenList(Node preNode, Node currNode) { if(currNode == null) { return preNode; } preNode.next = currNode; currNode.prev = preNode;
Node tempNext = currNode.next; Node tailNode = flattenList(currNode, currNode.child); currNode.child = null;
return flattenList(tailNode, tempNext); } }