Leetcodehot100(链表篇)

---

---

链表

相交链表

标题

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。假如两个链表不存在相交节点，返回 null 。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) {
7. *         val = x;
8. *         next = null;
9. *     }
10. * }
11. */
12. public class Solution {
13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14.         //la+c+lb
15.         //lb+c+la 走完全程一定会相遇
16.         //返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
17.         ListNode p=headA,q=headB;
18.         while(p!=q){
19.             p=p!=null?p.next:headB;
20.             q=q!=null?q.next:headA;
21.         }
22.         return p;
23.     }
24. }

复制代码

反转链表

标题

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode reverseList(ListNode head) {
13.         ListNode dummy=null;
14.         ListNode cur=head;
15.         while(cur!=null){
16.             ListNode next=cur.next;
17.             cur.next=dummy;
18.             dummy=cur;
19.             cur=next;
20.         }
21.         return dummy;
22.         
23.     }
24. }

复制代码

回文链表

标题

给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。假如是，返回 true ；否则，返回 false 。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public boolean isPalindrome(ListNode head) {
13.          // 计算链表长度
14.         int len = 0;
15.         ListNode cur = head;
16.         while (cur != null) {
17.             len++;
18.             cur = cur.next;
19.         }
21.         if (len == 0) return false;
23.         if (len % 2 == 0) {
24.             // 链表长度为偶数
25.             int halfLen = len / 2;
26.             ListNode cur1 = head;
27.             ArrayList<Integer> firstHalf = new ArrayList<>();
28.             ArrayList<Integer> secondHalf = new ArrayList<>();
30.             for (int i = 0; i < halfLen; i++) {
31.                 firstHalf.add(cur1.val);
32.                 cur1 = cur1.next;
33.             }
35.             for (int i = halfLen; i < len; i++) {
36.                 secondHalf.add(cur1.val);
37.                 cur1 = cur1.next;
38.             }
40.             Collections.reverse(secondHalf);
42.             for (int i = 0; i < halfLen; i++) {
43.                 if (!firstHalf.get(i).equals(secondHalf.get(i))) {
44.                     return false;
45.                 }
46.             }
47.             return true;
48.         } else {
49.             // 链表长度为奇数
50.             int halfLen = len / 2;
51.             int middlePos = (len + 1) / 2;
52.             int count = 1;
53.             ListNode cur2 = head;
54.             ArrayList<Integer> firstHalf = new ArrayList<>();
55.             ArrayList<Integer> secondHalf = new ArrayList<>();
57.             for (int i = 0; i < halfLen; i++) {
58.                 firstHalf.add(cur2.val);
59.                 cur2 = cur2.next;
60.                 count++;
61.                 if (count == middlePos) {
62.                     cur2 = cur2.next;
63.                 }
64.             }
66.             for (int i = halfLen + 1; i < len; i++) {
67.                 secondHalf.add(cur2.val);
68.                 cur2 = cur2.next;
69.             }
71.             Collections.reverse(secondHalf);
73.             for (int i = 0; i < halfLen; i++) {
74.                 if (!firstHalf.get(i).equals(secondHalf.get(i))) {
75.                     return false;
76.                 }
77.             }
78.             return true;
79.         }
80.     }
81. }

复制代码

环形链表

标题

给你一个链表的头节点 head ，判断链表中是否有环。
假如链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表现给定链表中的环，评测体系内部使用整数 pos 来表现链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数举行传递 。仅仅是为了标识链表的实际情况。
假如链表中存在环 ，则返回 true 。 否则，返回 false 。
代码

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) {
7. *         val = x;
8. *         next = null;
9. *     }
10. * }
11. */
12. public class Solution {
13.     public boolean hasCycle(ListNode head) {
14.         //快慢指针进行判断
15.         ListNode slow=head,fast=head;
16.         //快指针可以向后移动两步的话 让快慢指针移动
17.         while(fast!=null&&fast.next!=null){
18.             slow=slow.next;
19.             fast=fast.next.next;
20.             if(slow==fast) return true;
21.         }
22.         return false;
23.      }
24. }

复制代码

环形链表 II

标题

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 假如链表无环，则返回 null。
假如链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表现给定链表中的环，评测体系内部使用整数 pos 来表现链表尾连接到链表中的位置（索引从 0 开始）。假如 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数举行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
代码

1. /**
2. * Definition for singly-linked list.
3. * class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode(int x) {
7. *         val = x;
8. *         next = null;
9. *     }
10. * }
11. */
12. public class Solution {
13.     public ListNode detectCycle(ListNode head) {
14.         //返回链表开始入环的第一个节点
15.         //如果链表无环，则返回 null
16.         //链表如果有环的那个结点
17.         //快慢指针进行判断
18.         ListNode slow=head,fast=head;
19.         //快指针可以向后移动两步的话 让快慢指针移动
20.         while(fast!=null&&fast.next!=null){
21.             slow=slow.next;
22.             fast=fast.next.next;
23.             if(slow==fast){
24.                 //说明存在环  找环的入口节点
25.                 slow=head;
26.                 while(slow!=fast){
27.                     slow=slow.next;
28.                     fast=fast.next;
29.                 }
30.                 return slow;//相遇结点即是环的入口结点
31.             }
32.         }
33.         return null;
34.     }
35. }

复制代码

归并两个有序链表

标题

将两个升序链表归并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的全部节点构成的。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
13.         if (l1 == null && l2 == null) return null;
14.         if (l1 == null) return l2;
15.         if (l2 == null) return l1;
17.         // 定义一个虚拟头结点
18.         ListNode dummy = new ListNode(-1);
20.         // 定义遍历的指针
21.         ListNode pre = dummy;
23.         while (l1 != null && l2 != null) {
24.             // 如果当前list1的节点值小于等于list2当前的节点值
25.             if (l1.val <= l2.val) {
26.                 pre.next = l1;
27.                 l1 = l1.next;
28.                 pre = pre.next;
29.             } else {
30.                 pre.next = l2;
31.                 l2 = l2.next;
32.                 pre = pre.next;
33.             }
34.         }
36.         if (l1 != null) {
37.             pre.next = l1;
38.         }
39.         if (l2 != null) {
40.             pre.next = l2;
41.         }
43.         return dummy.next;
44.     }
45. }

复制代码

两数相加

标题

给你两个 非空 的链表，表现两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同情势返回一个表现和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
13.         ListNode dummy=new ListNode(0);//创建一个哑结点
14.         dummy.next=null;
15.         int carry=0;//表示进位
16.         ListNode cur=dummy;
17.         while(l1!=null||l2!=null||carry!=0){//有进位的话 需要继续循环
18.             int sum=0;
19.             if(l1!=null){
20.                 sum+=l1.val;
21.                 l1=l1.next;
22.             }
23.             if(l2!=null){
24.                 sum+=l2.val;
25.                 l2=l2.next;
26.             }
27.             sum+=carry;//加上进位 第一个数是没有进位的 进位是给下一个数用的
28.             carry=sum/10;//更新进位
29.             cur.next=new ListNode(sum%10);
30.             cur=cur.next;
32.         }
33.         return dummy.next;
34.     }
35. }

复制代码

删除链表的倒数第 N 个结点

标题

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode removeNthFromEnd(ListNode head, int n) {
13.         if(head==null){
14.             return null;
15.         }
16.         //策略 将n-1 节点直接指向n+1
17.         int len=0;
18.         ListNode p=head;
19.         while(p!=null){
20.             len++;
21.             p=p.next;
22.         }
23.         // 特殊情况处理：如果要删除的是头结点
24.         if (len == n) {
25.             return head.next;
26.         }
27.         //也就是正数len-n+1个结点 cur指针移动到len-n即可
28.         ListNode dummy=new ListNode(0);//创建一个哑结点
29.         dummy.next=head;
30.         ListNode cur=dummy.next;
31.         int pos=len-n;
32.         while(cur!=null){//pos:3
33.             pos--;
34.             if(pos==0){
35.                 cur.next=cur.next.next;
36.                 break;
37.             }
38.             cur=cur.next;
39.         }
40.         return dummy.next;
41.     }
42. }

复制代码

两两交换链表中的节点

标题

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完本钱题（即，只能举行节点交换）。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode swapPairs(ListNode head) {
13.         //给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
14.         //因为头结点改变 所以需要设置一个哑结点
15.         if(head==null||head.next==null) return head;
16.         ListNode dummy=new ListNode(0);
17.         dummy.next=head;
18.         ListNode cur=dummy.next;
19.         //处理链表至少有两个结点的情况
20.         //定义快慢指针
21.         ListNode slow=dummy.next;
22.         ListNode fast=dummy.next.next;
24.     }
25. }

复制代码

K 个一组翻转链表

标题

给你链表的头节点 head ，每 k 个节点一组举行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或便是链表的长度。假如节点总数不是 k 的整数倍，那么请将末了剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际举行节点交换。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode reverseKGroup(ListNode head, int k) {
13.         //统计节点个数
14.         int n=0;
15.         ListNode p=head;
16.         while(p!=null){ //这里头指针被改变了
17.             n++;
18.             p=p.next;
19.         }
20.         ListNode dummy=new ListNode(0);
21.         dummy.next=head;
22.         //用于翻转链表
23.         ListNode p0=dummy;
24.         ListNode pre=null;
25.         ListNode cur=head;
26.         //k个一组
27.         for(;n>=k;n-=k){
28.             for(int i=0;i<k;i++){//遍历k次
29.                 ListNode next=cur.next;
30.                 cur.next=pre;
31.                 pre=cur;
32.                 cur=next;
33.             }
34.             //创建哨兵节点  用于下一次遍历
35.             ListNode nxt=p0.next;
36.             p0.next.next=cur;
37.             p0.next=pre;
38.             p0=nxt;
39.         }
40.         return dummy.next;
41.     }
42.    
43. }

复制代码

随机链表的复制

标题

给你一个长度为 n 的链表，每个节点包含一个额外增长的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点构成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针可以或许表现相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，假如原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
代码

1. /*
2. // Definition for a Node.
3. class Node {
4.     int val;
5.     Node next;
6.     Node random;
8.     public Node(int val) {
9.         this.val = val;
10.         this.next = null;
11.         this.random = null;
12.     }
13. }
14. */
16. class Solution {
17.     public Node copyRandomList(Node head) {
18.         //定义一个hash表存储 原始结点与拷贝结点的映射关系
19.         Map<Node,Node> mp=new HashMap<>();
20.         for(Node cur=head;cur!=null;cur=cur.next){
21.             //每遍历到一个结点就创建一个拷贝结点 并创建映射关系
22.             mp.put(cur,new Node(cur.val));
23.         }
24.         //对边进行拷贝
25.         for(Node cur=head;cur!=null;cur=cur.next){
26.             if(cur.next!=null) mp.get(cur).next=mp.get(cur.next);
27.             if(cur.random!=null) mp.get(cur).random=mp.get(cur.random);
28.         }
29.         return mp.get(head);
30.     }
31. }

复制代码

排序链表

标题

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode sortList(ListNode head) {
13.         // 递归终止条件：如果链表为空或只有一个节点，直接返回
14.         if (head == null || head.next == null) {
15.             return head;
16.         }
18.         // 使用快慢指针找到链表的中间节点
19.         ListNode fast = head.next, slow = head;
20.         while (fast != null && fast.next != null) {
21.             slow = slow.next;      // 慢指针每次走一步
22.             fast = fast.next.next; // 快指针每次走两步
23.         }
25.         // 将链表从中间断开，分成左右两部分
26.         ListNode temp = slow.next; // temp 是右半部分的头节点
27.         slow.next = null;          // 将左半部分的尾节点指向 null
29.         // 递归排序左半部分和右半部分
30.         ListNode left = sortList(head);  // 排序左半部分
31.         ListNode right = sortList(temp); // 排序右半部分
33.         // 合并两个有序链表
34.         ListNode pre = new ListNode(0); // 创建一个虚拟头节点
35.         ListNode result = pre;         // result 用于保存合并后的链表头节点
37.         // 遍历两个链表，按顺序合并
38.         while (left != null && right != null) {
39.             if (left.val < right.val) {
40.                 pre.next = left; // 将 left 节点连接到结果链表
41.                 left = left.next; // 移动 left 指针
42.             } else {
43.                 pre.next = right; // 将 right 节点连接到结果链表
44.                 right = right.next; // 移动 right 指针
45.             }
46.             pre = pre.next; // 移动 pre 指针
47.         }
49.         // 处理剩余的节点（如果有）
50.         pre.next = left != null ? left : right;
52.         // 返回合并后的链表头节点
53.         return result.next;
54.     }
55. }

复制代码

归并 K 个升序链表

标题

给你一个链表数组，每个链表都已经按升序排列。
请你将全部链表归并到一个升序链表中，返回归并后的链表。
代码

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode() {}
7. * ListNode(int val) { this.val = val; }
8. * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public ListNode mergeKLists(ListNode[] lists) {
13.         // 如果链表数组为空，直接返回 null
14.         if (lists.length == 0) {
15.             return null;
16.         }
18.         // 创建一个虚拟头节点，用于简化边界条件处理
19.         ListNode d = new ListNode(-1);
20.         // p 是合并后链表的尾指针，初始指向虚拟头节点
21.         ListNode p = d;
23.         // 创建一个最小堆（优先队列），用于存储所有链表的头节点
24.         // 堆的大小为链表的数量，比较规则是按节点的值升序排列
25.         PriorityQueue<ListNode> qu = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);
27.         // 遍历链表数组，将所有非空链表的头节点加入堆中
28.         for (ListNode node : lists) {
29.             if (node != null) {
30.                 qu.add(node);
31.             }
32.         }
34.         // 不断从堆中取出最小节点，连接到合并后的链表中
35.         while (!qu.isEmpty()) {
36.             // 取出堆中的最小节点
37.             ListNode node = qu.poll();
38.             // 将最小节点连接到合并后的链表中
39.             p.next = node;
40.             // 如果最小节点的下一个节点不为空，将其加入堆中
41.             if (node.next != null) {
42.                 qu.add(node.next);
43.             }
44.             // 移动 p 指针，使其指向新的尾节点
45.             p = p.next;
46.         }
48.         // 返回合并后的链表头节点（虚拟头节点的下一个节点）
49.         return d.next;
50.     }
51. }

复制代码

LRU 缓存

标题

请你操持并实现一个满意 LRU (近来最少使用) 缓存 束缚的数据布局。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 假如关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 假如关键字 key 已经存在，则变更其数据值 value ；假如不存在，则向缓存中插入该组 key-value 。假如插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
代码

1. class LRUCache {
2.     // LRU (最近最少使用) 缓存 least recently used
3.     private final int capacity;//定义一个缓存容量
4.     private final Map<Integer,Integer> cache=new LinkedHashMap<>();//自带双向链表的哈希表
6.     public LRUCache(int capacity) {
7.         this.capacity=capacity;
8.     }
9.    
10.     public int get(int key) {
11.         Integer value=cache.remove(key);
12.         if(value!=null){
13.             cache.put(key,value);//把key移到链表末尾
14.             return value;
15.         }
16.         return -1;
17.     }
18.    
19.     public void put(int key, int value) {
20.         if(cache.remove(key)!=null){
21.             cache.put(key,value);
22.             return;
23.         }
24.         if(cache.size()==capacity){
25.             Integer oldestKey=cache.keySet().iterator().next();
26.             cache.remove(oldestKey);//然后移除
27.         }
28.         cache.put(key,value);
29.     }
30. }
32. /**
33. * Your LRUCache object will be instantiated and called as such:
34. * LRUCache obj = new LRUCache(capacity);
35. * int param_1 = obj.get(key);
36. * obj.put(key,value);
37. */

复制代码

后续内容持续更新~~~


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。