太原网站制作机构,邢台做网站推广报价,网站租服务器,永州网站开发公司LeetCode 热题 HOT 100#xff1a;https://leetcode.cn/problem-list/2cktkvj/ 文章目录 2. 两数相加19. 删除链表的倒数第 N 个结点21. 合并两个有序链表23. 合并 K 个升序链表141. 环形链表142. 环形链表 II148. 排序链表160. 相交链表206. 反转链表234. 回文链表 2. 两数相… LeetCode 热题 HOT 100https://leetcode.cn/problem-list/2cktkvj/ 文章目录 2. 两数相加19. 删除链表的倒数第 N 个结点21. 合并两个有序链表23. 合并 K 个升序链表141. 环形链表142. 环形链表 II148. 排序链表160. 相交链表206. 反转链表234. 回文链表 2. 两数相加
题目链接https://leetcode.cn/problems/add-two-numbers/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
实现步骤
将两个链表看成是相同长度的进行遍历如果一个链表较短则在前面补 0比如987 23 987 023 1010。每一位计算的同时需要考虑上一位的进位问题而当前位计算结束后同样需要更新进位值。如果两个链表全部遍历完毕后进位值为 1则在新链表最前方添加节点。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre new ListNode(0);ListNode p1 l1, p2 l2, q pre;int sign 0;while(p1 ! null || p2 ! null){int sum 0;if(p1 null){sum p2.val sign;p2 p2.next;}else if(p2 null){sum p1.val sign;p1 p1.next;}else{sum p1.val p2.val sign;p1 p1.next;p2 p2.next;}sign sum 10 ? 1 : 0; // 修改标志位ListNode node new ListNode(sum % 10);q.next node;q q.next;}if(sign 1){ListNode node new ListNode(1);q.next node;}return pre.next;}
}19. 删除链表的倒数第 N 个结点
题目链接https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre new ListNode(0); // 伪头部节点pre.next head;ListNode p, q;p q pre;int co 0;while(q.next ! null){ // 先让q指针先走n步然后p指针再继续走if(co n){p p.next;}q q.next;}// 结束循环时p指针指向倒数第N1位p.next p.next.next;// 注意避坑点return head; 是存在问题的当链表中只有一个元素时p指针会进行删除后head 还是指向原来的那个结点。return pre.next; }
}21. 合并两个有序链表
题目链接https://leetcode.cn/problems/merge-two-sorted-lists/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode res new ListNode(0);ListNode p res;while(list1 ! null list2 ! null){if(list1.val list2.val){p.next list1;list1 list1.next;}else{p.next list2;list2 list2.next;}p p.next;}p.next list1 null ? list2 : list1;return res.next;}
}23. 合并 K 个升序链表
题目链接https://leetcode.cn/problems/merge-k-sorted-lists/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode head null;for(int i 0; i lists.length; i ){head mergeTwoLists(head, lists[i]);}return head;}public ListNode mergeTwoLists(ListNode a, ListNode b){ListNode res new ListNode(0);ListNode p res;while(a!null b!null){if(a.val b.val){p.next a;a a.next;}else{p.next b;b b.next;}p p.next;}p.next a ! null ? a : b;return res.next;}
}141. 环形链表
题目链接https://leetcode.cn/problems/linked-list-cycle/description/?envTypestudy-plan-v2envIdtop-100-liked
哈希表做法时间复杂度较高
public class Solution {public boolean hasCycle(ListNode head) {if(head null){return false;}SetListNode set new HashSet(); // set 记录结点的地址while(head.next ! null){if(set.contains(head)){return true;}set.add(head);head head.next;}return false;}
}快慢指针做法1
public class Solution {public boolean hasCycle(ListNode head) {if(head null){return false;}ListNode slow, fast;slow head;fast head.next;// slow 每次向前走一步fast 每次向前走两步可以任意多步// 当存在环时fast 由于走得快会发生扣圈的情况且最终与 slow 相遇// 当不存在环时fast 可能在某次循环后发生当前位置为空或下一位置为空的两种情况当然由于走的快最终会返回false。// 总之循环的结束条件要么出现环 slow fast要么 fast 先一步为空 while(slow ! fast fast ! null fast.next ! null){// 注意fast ! null 要先于fast.next ! null 来判断以防止控制帧异常slow slow.next;fast fast.next.next;}return slow fast;}
}快慢指针做法2思路同下方“环形链表2”
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow head, fast head;while(true){if(fastnull || fast.nextnull){return false;}slow slow.next;fast fast.next.next;if(slowfast){return true;}}}
}142. 环形链表 II
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/?envTypestudy-plan-v2envIdtop-100-liked
哈希表做法时间复杂度较高
public class Solution {public ListNode detectCycle(ListNode head) {SetListNode set new HashSet();ListNode p head;while(p!null){if(set.contains(p)){return p;}set.add(p);p p.next;}return null;}
}快慢指针实现思路如下
设 fast 每次走两个节点 slow 每次走一个节点。环外有 a 个结点环内有 b 个结点。相遇时fast 走了 f 步slow 走了 s 步。 ① f 2s ② f s nb 表示 f 比 s 多走了 n*b 步即 n 圈。这样表示的原因在于扣圈。 化简得f 2nb, s nb设刚开始 slow 指针从开始到环的入口要走 k 步k a nb n 0,1,2,…由于 s n*b即已经走了 n*b 步了那么此时只需要再走 a 步即可回到链表入环的起点。
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head, slow head;while(true){if(fast null || fast.next null){return null;}fast fast.next.next;slow slow.next;if(fast slow){break;}}fast head; // fast回到链表起点与 slow 一同遍历 a 步while(slow ! fast){slow slow.next;fast fast.next;}return fast;}
}148. 排序链表
题目链接https://leetcode.cn/problems/sort-list/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
使用优先队列模仿堆
class Solution {public ListNode sortList(ListNode head) {PriorityQueueListNode queue new PriorityQueue((a, b) - b.val-a.val); // 大顶堆while(head ! null){queue.offer(head); // 从堆底插入head head.next;}ListNode pre new ListNode(0);while(!queue.isEmpty()){ListNode p queue.poll(); // 出队列并调整堆p.next pre.next; // 头插法倒序pre.next p;}return pre.next;}
}自顶向下归并排序1 时间复杂度 O(nlogn)空间复杂度O(logn)
class Solution {public ListNode sortList(ListNode head) {return mergeSort(head, null);}// 归并排序// 将头指针和尾指针之前的元素进行排序初始尾指针为null即最后一个节点的下一个空节点public ListNode mergeSort(ListNode head, ListNode tail){if(head tail){return head;}if(head.next tail){ // 隔离出来单独结点head.next null;return head;}ListNode slow, fast;slow fast head;while(fast ! tail){slow slow.next;fast fast.next;if(fast ! tail){fast fast.next;}}ListNode mid slow;ListNode l1 mergeSort(head, mid); // 将 head 至 mid 之前的节点进行排序ListNode l2 mergeSort(mid, tail); // 将 mid 至 tail 之前的节点进行排序return mergeList(l1, l2);}// 合并两个有序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre new ListNode(0);ListNode p pre;while(l1 ! null l2 ! null){if(l1.val l2.val){p.next l1;l1 l1.next;}else{p.next l2;l2 l2.next;}p p.next;}p.next l1 null ? l2:l1;return pre.next;}
}参考链接https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/?envTypefeatured-listenvId2cktkvj%3FenvType%3Dfeatured-listenvId2cktkvj
自顶向下归并排序2
class Solution {public ListNode sortList(ListNode head) {return mergeSort(head);}// 归并排序public ListNode mergeSort(ListNode head){if(headnull || head.nextnull){return head;}ListNode slow head; // 快慢指针ListNode fast head.next;while(fast!null fast.next!null){ // 查询中间节点slow slow.next;fast fast.next.next;}ListNode mid slow.next; // 断链slow.next null;ListNode l1 mergeSort(head);ListNode l2 mergeSort(mid);return mergeList(l1, l2);}// 合并两个有序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre new ListNode(0);ListNode p pre;while(l1 ! null l2 ! null){if(l1.val l2.val){p.next l1;l1 l1.next;}else{p.next l2;l2 l2.next;}p p.next;}p.next l1 null ? l2:l1;return pre.next;}
}自底向上排序 时间复杂度 O(nlog)空间复杂度O(n)
class Solution {public ListNode sortList(ListNode head) {ListNode pre new ListNode(0);pre.next head;int len getLength(head); // 获取长度for(int step 1; step len; step *2){ //依次将链表分块的长度分为124...ListNode curr pre.next;ListNode p pre;// p 用于链接每次分块的链表如第一次循环链接分块长度为1的链表然后链接分块长度为2的链表while(curr ! null){ListNode h1 curr; // 第一块链表的头ListNode h2 spilt(h1, step); // 第二块链表的头curr spilt(h2, step); // 下次while循环的头也是给到h1// 合并第一二块链表下次while循环合并第三四块链表....ListNode res mergeList(h1, h2);// 将合并后的链表链接起来并将指针移到链表的最后一个节点以链接下次的链表p.next res;while(p.next!null){p p.next;}}}return pre.next;}// 分割链表并返回后半段的链头public ListNode spilt(ListNode head, int step){if(head null){return null;}ListNode p head;for(int i 1; i step p.next!null; i ){p p.next;}ListNode right p.next;p.next null; // 切断连接return right;}// 求链表长度public int getLength(ListNode head){int co 0;while(head!null){co;head head.next;}return co;}// 合并两个升序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre new ListNode(0);ListNode p pre;while(l1 ! null l2 ! null){if(l1.val l2.val){p.next l1;l1 l1.next;}else{p.next l2;l2 l2.next;}p p.next;}p.next l1 null ? l2:l1;return pre.next;}
}160. 相交链表
题目链接https://leetcode.cn/problems/intersection-of-two-linked-lists/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
实现步骤
设不是公共部分的节点数分别是 a、b公共节点数为 n。如果有公共节点则当 p1 遍历完 an 个节点时再在另一个链表的头部遍历 b 个节点时必相交。原因在于此时 p2 遍历了 bna 个结点。如果没有公共节点部分那么 p1 与 p2 经历了上文的步骤后都会为 null nullnull 为 true。 因此跳出循环要么 null null要么都不为空找到了公共节点。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 headA;ListNode p2 headB;while(p1 ! p2){p1 p1 null ? headB : p1.next;p2 p2 null ? headA : p2.next;}return p1;}
}206. 反转链表
题目链接https://leetcode.cn/problems/reverse-linked-list/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public ListNode reverseList(ListNode head) {ListNode pre new ListNode(0);ListNode p head;while(p!null){ListNode q p.next;p.next pre.next;pre.next p;p q;}return pre.next;}
}234. 回文链表
题目链接https://leetcode.cn/problems/palindrome-linked-list/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public boolean isPalindrome(ListNode head) {DequeListNode stack new LinkedList();ListNode p head;while(p!null){stack.push(p);p p.next;}while(head ! null){p stack.pop();if(p.val ! head.val){return false;}head head.next;}return true;}
}
