链表
链表
第七个专题
相交链表
题目链接：相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
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 中第四个节点) 在内存中指向相同的位置。
思路一：将第一个链表的每个节点存入set中，然后遍历第二个链表的每一个节点，查看是否存在于set中，第一个存在的便是答案，如果不存在返回空（哈希思想）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> st = new HashSet<>();
ListNode temp = headA;
while(temp != null){
st.add(temp);
temp = temp.next;
}
temp = headB;
while(temp !=null){
if(st.contains(temp)){
return temp;
}
temp = temp.next;
}
return null;
}
}思路二：双指针，两个链表中节点相互比较，比较完成后同时转至下一节点，如果某个链表遍历完了，也就是遍历到null了，就跳转至另一个列表的头节点，以此往复总会有某一刻遍历到相交的节点，如果不相交，也总会有一刻遍历到null，只要两个节点相同就返回该节点
情况一：两个链表相交
链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。
如果 a=b，则两个指针会同时到达两个链表相交的节点，此时返回相交的节点；
如果 a!=b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
情况二：两个链表不相交
链表 headA 和 headB 的长度分别是 m 和 n。考虑当 m=n 和 m!=n 时，两个指针分别会如何移动：
如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；
如果 m!=n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA 移动了 m+n 次、指针 pB 移动了 n+m 次之后，两个指针会同时变成空值 null，此时返回 null。/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode lnA = headA;
ListNode lnB = headB;
while(lnA != lnB){
lnA = lnA == null ? headB : lnA.next;
lnB = lnB == null ? headA : lnB.next;
}
return lnA;
}
}反转链表
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：
思路：一边遍历一遍反转，一定要理解好节点之间的关系
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode temp = head;
ListNode prev = null;
while(temp != null){
ListNode next = temp.next;//用next存储下一节点
temp.next = prev;//将当前节点指向前一节点
prev = temp;//前一节点后移
temp = next;//当前节点后移
}
return prev;
}
}回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
思路一：用数组存链表的值，然后双指针比较
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode temp = head;
List<Integer> ls = new ArrayList<>();
while(temp!=null){
ls.add(temp.val);
temp = temp.next;
}
int left = 0;
int right = ls.size()-1;
while(left<right){
if(ls.get(left).equals(ls.get(right))){
left++;
right--;
}else{
return false;
}
}
return true;
}
}思路二：符合常规思维，将后半段做一个反转，然后从头比较两两是否相等，思路很简单，但是代码书写比较麻烦，这个的空间复杂度为O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null){
return true;
}
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverse(firstHalfEnd.next);
ListNode p1 = head;
ListNode p2 = secondHalfStart;
while(p1 != null &&p2 != null){
if(p1.val != p2.val){
reverse(secondHalfStart);
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
}
private ListNode reverse(ListNode head){
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast.next != null&&fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}环形链表
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路一：使用哈希，将遍历到的节点用set存储起来，然后顺着链表节点遍历，如果后边某个节点在set中发现了，则说明出现了回环
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}思路二：采用快慢指针，因为存在回环，所以两个指针终会碰到，如果碰到null则说明无回环，则返回false
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast.next == null || fast.next.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}合并两个有序链表
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路一：递归，因为返回值为合并后的头节点，所以两个头节点比较后，递归调用较小值的next和较大值并作为较小值的新next，注意前提判断，如果有一个头节点为空则返回为另一个链表头节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//前置条件，不仅仅说明一个初始一个链表为空，答案肯定是另一个链表；也说明一个链表遍历结束，直接把另一个链表剩余节点直接连接上
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}else if(list1.val < list2.val){
//递归调用
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next = mergeTwoLists(list2.next,list1);
return list2;
}
}
}递归其实按照常规思维并不容易想到，更容易想到的应该是两两比较，再做节点连接，实际上，这种常规的迭代思维空间复杂度更低
思路二：常规迭代
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//先做了空对象判断
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}
//对结果头节点做了初始化
ListNode result = list1.val < list2.val ? list1 : list2;
if(list1.val < list2.val){
list1 = list1.next;
}else{
list2 = list2.next;
}
//使用prev临时记录当前节点
ListNode prev = result;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
prev.next = list1;
prev = list1;
list1 = list1.next;
}else{
prev.next = list2;
prev = list2;
list2 = list2.next;
}
}
//当一个链表到null时，另一个可能没有遍历完，直接加到末尾
prev.next = list1 == null? list2:list1;
return result;
}
}
//这个符合常规逻辑，但是开始有些繁琐，因为我们过于着急的先去比较两个头节点，逻辑有些混乱，官方题解使用一个前置最小节点解决了这个问题官方迭代题解：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}两数相加
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
思路：思路其实很简单，模拟数值相加就行，要注意的是进位的问题，以及链表末尾会不会进位
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null;
ListNode tail = null;
int carry = 0;
while( l1 != null || l2 != null){
int x;
int y;
if(l1 == null){
x = 0;
}else{
x = l1.val;
}
if(l2 == null){
y = 0;
}else{
y = l2.val;
}
int sum = x + y + carry;
if(head == null){
head = tail = new ListNode(sum%10);
}else{
tail.next = new ListNode(sum%10);
tail = tail.next;
}
carry = sum/10;
if(l1!=null){
l1 = l1.next;
}
if(l2!=null){
l2 = l2.next;
}
// 如果末尾有进位
if(l1 == null && l2 == null && carry !=0){
tail.next = new ListNode(carry);
}
}
return head;
}
}删除链表的倒数第 N 个结点
删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
思路：找到，要删的节点的前一个节点，然后设置该节点的next为该节点next的next，因为不是双向链表，所以不能倒叙寻找，得先确定链表长度。并且我们要使用一个哑节点，置于头节点前面，因为如果链表只有一个节点，我们要删掉这个节点那么。head.next = head.next.next时就会编译错误，这是因为head.next为空不存在它的next。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
ListNode temp = dummy;
int length = getLength(head);
for (int i = 0; i < length - n; i++) {
temp = temp.next;
}
temp.next = temp.next.next;
return dummy.next;
}
public int getLength(ListNode head){
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
}两两交换链表中的节点
两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
题目感觉不难，但是有很多细节需要考虑，比如判断条件，比如两两交换后节点的指向问题。
思路一：使用递归的方法，方法输入头节点返回的是一个两两交换后的链表，那么我们只需要将head节点的next设为swapPairs(head.next.next)，然后head.next指向head，返回结果为head.next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 链表长度为0或者为1，不需要交换直接返回就行
if(head == null || head.next == null){
return head;
}
// 返回节点即为head.next
ListNode res = head.next;
// 递归调换
head.next = swapPairs(res.next);
res.next = head;
return res;
}
}思路二：迭代思想，这个是比较容易想到的思路，空间复杂度也更小，但是有很多细节问题需要考虑，同时使用一个预设节点更加方便
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 预设节点，置于头节点前方，答案即为该节点的next
ListNode beforeHead = new ListNode(0);
beforeHead.next = head;
// 使用temp进行迭代，便于答案返回
ListNode temp = beforeHead;
while(temp.next != null && temp.next.next != null){
// 每次操作都是三个节点
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
node1.next = node2.next;
node2.next = node1;
temp.next = node2;
temp = node1;
}
return beforeHead.next;
}
}两两交换链表中的节点
两两交换链表中的节点
给你一个长度为 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 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
这个题目，乍一看挺简单，但是这个随机节点在使绊子。复制过程中，可能出现随机节点没有创建的情况，这个题目重点也是解决这个问题。
思路一：回溯+哈希 每次复制时，检查一个全局map，查看该节点的next或random节点是否创建了，如果没有就递归调用先将next或者random节点进行创建
class Solution {
Map<Node, Node> cachedMap = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if(!cachedMap.containsKey(head)){
Node headNew = new Node(head.val);
cachedMap.put(head, headNew);
headNew.next = copyRandomList(head.next);
headNew.random = copyRandomList(head.random);
}
return cachedMap.get(head);
}
}思路二：注意到方法一需要使用哈希表记录每一个节点对应新节点的创建情况，而我们可以使用一个小技巧来省去哈希表的空间。
我们首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 A→B→C，我们可以将其拆分为 A→A′→B→B′→C→C′ 。对于任意一个原节点 S，其拷贝节点 S′即为其后继节点。
这样，我们可以直接找到每一个拷贝节点 S′的随机指针应当指向的节点，即为其原节点 S 的随机指针指向的节点 T 的后继节点 T′。需要注意原节点的随机指针可能为空，我们需要特别判断这种情况。
当我们完成了拷贝节点的随机指针的赋值，我们只需要将这个链表按照原节点与拷贝节点的种类进行拆分即可，只需要遍历一次。同样需要注意最后一个拷贝节点的后继节点为空，我们需要特别判断这种情况。
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 在每个节点后面复制节点
for(Node node = head; node != null; node = node.next.next){
Node newNode = new Node(node.val);
newNode.next = node.next;
node.next = newNode;
}
// 将复制节点的random进行正确指向
for(Node node = head; node != null; node = node.next.next){
Node newNode = node.next;
newNode.random = node.random == null ? null : node.random.next;
}
// 设置返回头节点
Node newHead = head.next;
// 拆分
for(Node node = head; node != null; node = node.next){
Node newNode = node.next;
node.next = node.next.next;
newNode.next = newNode.next == null ? null : newNode.next.next;
}
return newHead;
}
}排序链表
排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
思路一：自顶向下，结合之前合并排序链表的方法，将该链表递归二分，分为两部分，然后排序合并，结合之前的方法进行
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
// 递归方法，排序该头节点到尾节点，tail不能取到
public ListNode sortList(ListNode head,ListNode tail){
if(head ==null){
return head;
}
if(head.next == tail){
head.next =null;
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast!=tail){
slow = slow.next;
fast = fast.next;
if(fast != tail){
fast = fast.next;
}
}
ListNode mid = slow;
ListNode l1 = sortList(head,mid);
ListNode l2 = sortList(mid,tail);
return merge(l1,l2);
}
public ListNode merge (ListNode l1,ListNode l2){
ListNode preHead = new ListNode(-1);
ListNode pre = preHead;
while(l1 != null && l2 != null){
if(l1.val<l2.val){
pre.next = l1;
l1=l1.next;
}else{
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = l1 == null ? l2:l1;
return preHead.next;
}
}