一般网站 要 加入 友情链接吗,网站代运营要多少费用吗,大连网站哪家做的好,开一个网站需要什么手续一.删除链表中与val相等的所有节点
1.题目描述 ----- 203. 移除链表元素 - 力扣#xff08;LeetCode#xff09; 给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。 列表中的节点数目在范…一.删除链表中与val相等的所有节点
1.题目描述 ----- 203. 移除链表元素 - 力扣LeetCode 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 列表中的节点数目在范围 [0, 10^4] 1 Node.val 500 val 50 2.思路分析
思路分析: 快慢指针: 定义一个slow指针和一个fast指针;
fast指针用于遍历链表, 查找链表和val相同的节点slow指针用于删除fast查找的和val相同的节点fast指向和val相同的节点时, 让slow的下一个指向fast的下一个(不是slow改变了, 是它的下一个指向改变), fast后移; fast指向和val不相等的节点时, 直接让slow指向fast, fast后移
3.算法过程
定义快慢指针, 快指针用于遍历链表, 慢指针用于删除和val相同的节点 slow head; fast head.next;遍历链表, 把和val相同的节点都删掉 a. 快指针的val是否和给定的val相同 slow.next fast.next; fast fast.next;快指针的val和给定的val不相同 slow fast; fast fast.next;判断头节点: 因为我们是从第二个节点开始判断的 if(head.val val) head head.next;
4.代码详解
class Solution {public ListNode removeElements(ListNode head, int val) {// 判空if (head null) return head;// 定义前驱和后继// 前驱用于指向不是和 val 相等的节点// 后继用于遍历链表ListNode prev head;ListNode cur head.next;while (cur ! null) {// 节点值和 val 相等if (cur.val val) {// 让前驱 prev 指向后继 cur 的下一个节点处prev.next cur.next;} else {// 不相等让前驱 prev 走一步prev prev.next;}// 继续判断下一个节点cur cur.next;}// 头节点和 val 相等的情况if (head.val val) {head head.next;}// 返回修改后的链表return head;}
} 二.反转链表
1.题目描述 ----- 206. 反转链表 - 力扣LeetCode 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 2.思路分析
思路分析: 遍历头插: 使用cur指针进行边遍历边头插
让cur指针指向head的下一个节点, 遍历cur;使用curNext指针指向cur的下一个节点, 即记录cur的下一节点的位置进行头插, 把cur的下一个指向head, 让head又指向curcur重新指向curNext, 即保存了cur的下一个节点的指针
3.算法过程
head为空, 直接返回head if(head null) return head;定义cur, cur指向head.next cur head.next;把head.next置空, 防止形成环 head.next null;遍历cur链表 保存cur的下一个节点的位置, 防止找不到无法进行反转 curNext cur.next;进行头插法 cur.next head; head cur;cur指向下一个节点(遍历) cur curNext;返回反转后的链表 return head;
4.代码详解
class Solution {public ListNode reverseList(ListNode head) {// 判空if (head null) return head;// 获取头节点之后的节点ListNode cur head.next;// 把头节点之后的节点置空防止循环链表head.next null;// 当 cur 为空后跳出循环while (cur ! null) {// 获取 cur 的下一个节点ListNode curNext cur.next;// 头插cur.next head;head cur;// cur 重新指向 cur 的下一个节点cur curNext;}// 返回翻转后的头节点return head;}
} 三.返回链表的中间节点
1.题目描述 ----- 876. 链表的中间结点 - 力扣LeetCode 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 链表的结点数范围是 [1, 100]1 Node.val 100 2.思路分析
思路分析: 快慢指针
当快指针的速度是慢指针的2倍时, 快指针走完链表后, 慢指针刚好到链表的中间位置
3.算法过程
定义快慢指针 fast head; slow head;遍历链表, 快指针每次走两步, 慢指针每次走一步 fast fast.next.next; slow slow.next;链表结束条件: 快指针走的快, 当快指针走完链表, 即遍历结束 while(fast ! null fast.next ! null);
4.代码详解
class Solution {public ListNode middleNode(ListNode head) {// 定义快慢指针ListNode slow head;ListNode fast head;// fast 为空或 fast.next 为空则跳出循环while (fast ! null fast.next ! null) {// slow 走一步slow slow.next;// fast 走两步fast fast.next.next;}// 返回中间节点return slow;}
} 四.输出链表的倒数第k个节点
1.题目描述 ----- 面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode 实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。 给定的 k 保证是有效的。 2.思路分析
思路分析: 快慢指针
快指针先走k步后, 此时快慢指针的差距是k步, 然后快慢指针一起走, 快指针走完链表后, 慢指针走到倒数第k个位置处
3.算法过程
定义快慢指针 fast head; slow head;快指针先走k步 for(i 0; i k; i) fast fast.next;快慢指针一起走,快指针走完,慢指针到倒数第k个位置处 while(fast ! null) fast fast.next; slow slow.next;返回倒数第k个位置处的值 return slow.val;
4.代码详解
class Solution {public int kthToLast(ListNode head, int k) {// 定义快慢指针ListNode slow head;ListNode fast head;// 让 fast 先走 k 步for (int i 0; i k; i) {fast fast.next;}// 此时fast 已经领先 slow k 步// 两个一起走当 fast 到达最后一个节点的时候slow 走到第 k 个节点while (fast ! null) {fast fast.next;slow slow.next;}// 返回 slow 处的值return slow.val;}
} 五.合并有序链表
1.题目描述 ----- 21. 合并两个有序链表 - 力扣LeetCode 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 l2 非递减顺序 2.思路分析
思路分析: 模拟
比较节点的大小, 那个值小则把该节点放到connection链表的后面, 那个链表为空后, 则把另一个链表放在connection的后面;
3.算法过程
定义连接节点和新的头节点 connection new ListNode(); head connection;循环遍历, 当list1和list2均空则跳出循环 list1为空, 则把list2的所有节点放到connection的后面, 跳出循环 connection.next list2; break;list2为空, 则把list1的所有节点放到connection的后面, 跳出循环 connection.next list1; break;若list1.val list2.val connection.next list1; list1 list1.next; //后移 connection connection.next; //后移若list1.val list2.val connection.next list1; list1 list1.next; //后移 connection connection.next; //后移返回头节点 return head.next;
4.代码详解
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 其中一个链表为空if (list1 null) return list2;if (list2 null) return list1;// 定义连接链表ListNode dummy new ListNode();// 定义新的头节点ListNode newHead dummy;// 当 list1 和 list2 均为空跳出循环while (list1 ! null || list2 ! null) {if (list1 null) {// list1 为空把 list2 的节点全部放在 dummy 后面dummy.next list2;break;} else if (list2 null) {// list2 为空把 list1 的节点全部放在 dummy 后面dummy.next list1;break;} else if (list1.val list2.val) {// list1 节点值小于 list2 节点值把 list1 的节点放在 dummy 后面dummy.next list1;// 让 list1 走到下一个节点处list1 list1.next;} else {// list2 节点值小于 list1 节点值把 list2 的节点放在 dummy 后面dummy.next list2;// 让 list2 走到下一个节点处list2 list2.next;}// 让 dummy 走到下一个节点处dummy dummy.next;}// 返回头节点return newHead.next;}
} 六.分割链表
1.题目描述 ----- 面试题 02.04. 分割链表 - 力扣LeetCode 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 链表中节点的数目在范围 [0, 200] -100 Node.val 100-200 x 200 2.思路分析
思路分析: 模拟
定义四个链表, minVal链表存储比x小的节点, maxVal链表存储比x大的节点; minHead指向minVal, maxHead指向maxVal循环head链表, 把比x小的节点放入到minVal链表中, 比x大的节点放入到maxVal链表中防止形成环, 把maxVal.next置为空, 因为最大的值不一定是最后一个连接两个链表, 并返回新链表的头节点
3.算法过程
创建两个链表,定义头节点 minVal, maxVal new ListNode(); minHead minVal; maxHead maxVal;循环head链表, 把节点值小于x的放到minVal中, 比x大的放入到maxVal中 if(cur.val x) minVal.next cur; minVal minVal.next; else maxVal.next cur; maxVal maxVal.next;把maxVal的next置为空, 防止形成环 maxVal.next null;连接两个链表 minVal.next maxHead.next;返回新链表 return minHead.next;
4.代码详解
class Solution {public ListNode partition(ListNode head, int x) {// 使用 prev 来获取小于 x 值的链表节点ListNode prev new ListNode();// 指向 prev 的节点用于后续返回结果ListNode newHead prev;// 使用 last 来获取 大于等于 x 值的链表节点ListNode last new ListNode();// 使用 headLast来指向 last 的头节点方便连接ListNode headLast last;// 遍历链表节点ListNode cur head;// 为空跳出循环while (cur ! null) {// 小于 x 的链表节点值的节点都放在 prev 链表下if (cur.val x) {prev.next cur;prev prev.next;} else {// 大于等于 x 的链表节点值的节点都放在 last 链表下last.next cur;last last.next;}// cur 获取下一个节点cur cur.next;}// 防止 last 的最后一个节点不是链表的最后一个节点last.next null;// 连接prev.next headLast.next;// 返回return newHead.next;}
} 七.回文链表
1.题目描述 ----- LCR 027. 回文链表 - 力扣LeetCode 给定一个链表的 头节点 head 请判断其是否为回文链表。 如果一个链表是回文那么链表节点序列从前往后看和从后往前看是相同的。 链表 L 的长度范围为 [1, 10^5]0 node.val 9 2.思路分析
思路分析: 快慢指针 头插法 前后指针比较
定义快慢指针, 找到中间节点把中间节点之后的元素都进行头插使用slow指针和fast指针比较值, 不同则不是回文
3.算法过程
定义快慢指针 fast head; slow head;循环链表, 快指针每次走两步, 慢指针每次走一步, 找到中间节点 fast fast.next.next; slow slow.next;在中间节点进行头插 curNext cur.next; cur.next slow; slow cur; cur curNext;重置快指针, 快慢指针相等则说明为回文链表 fast head; while(fast ! slow) if(fast.val ! slow.val) return false; if(fast.next slow) return true; // 偶数个节点跳出循环, 说明是回文链表 return true;
4.代码详解
class Solution {public boolean isPalindrome(ListNode head) {// 定义快慢指针ListNode fast head;ListNode slow head;// fast 为空或 fast.next为空跳出循环while(fast ! null fast.next ! null) {// fast 每次走两步fast fast.next.next;// slow 每次走一步slow slow.next;}// 头插// 把 slow 后面的节点进行头插ListNode cur slow.next;while(cur ! null) {// 记录 cur 的下一个节点ListNode curNext cur.next;// 头插cur.next slow;// 重置头节点slow cur;// 获取下一个节点cur curNext;}// 重置 fastfast head;// 当相遇时跳出循环说明是回文链表while(fast ! slow) {// 值不相等则说明不是回文链表if(fast.val ! slow.val) {return false;}// 节点为偶数个的回文链表if(fast.next slow) {break;}// fast 和 slow 均走一步fast fast.next;slow slow.next;}// 返回结果return true;}
} 八.链表的公共节点
1.题目描述 ----- 160. 相交链表 - 力扣LeetCode 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 listA的数目为 mlistB的数目为n1 m, n 3 * 10^41 Node.val 10^50 skipA m0 skipB n如果 listA 和listB 没有交点, intersectVal 为0 如果 listA 和listB 有交点, intersectVal listA[skipA] listB[skipB] 2.思路分析
思路分析: 模拟.
获取两个两个链表的长度, 判断出谁长, 使用一个引用指向最长的那个链表, 另一个引用指向最短的那个链表;让最长的那个链表先走两个链表的差值步, 然后两个一起走, 即可得到相遇点
3.算法过程
获取两个链表的长度 l1 size(A); l2 size(B);区分最长和最短的链表, 获取两者的差值步 cur1 最长的链表; cur 最短的链表; gap size(长链表) - size(短链表);让最长的链表先走两者的差值步 for(int i 0; i gap; i) cur1 cur1.next;长短链表一起走, 相遇即是相遇点 while(cur1 ! cur2) cur1 cur1.next; cur2 cur2.next;返回相遇点 return cur1;
4.代码详解
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// cur1 用来指向长度最长的链表默认是 headAListNode cur1 headA;// cur2 用来指向长度最短的链表默认是 headBListNode cur2 headB;// 计算两个链表的长度int size1 count(headA);int size2 count(headB);// 用来获取两个链表的长度差int gap 0;if (size1 size2) {// 这个地方说明 headA 的链表长度最长// 计算两个链表的长度差即可gap size1 - size2;} else {// 这个地方说明 headB 的链表长度最长// 重置 cur1 和 cur2让他们分别指向最长和最短的链表cur1 headB;cur2 headA;// 链表长度的差值gap size2 - size1;}// 让最长的链表先走差值步for (int i 0; i gap; i) {cur1 cur1.next;}// 两个链表一起走相等则说明走到了公共节点while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}// 返回公共节点return cur1;}// 计算链表的节点数private int count(ListNode head) {int count 0;ListNode cur head;while (cur ! null) {count;cur cur.next;}return count;}
} 九.判断链表是否有环
1.题目描述 ----- 141. 环形链表 - 力扣LeetCode 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 如果链表中存在环 则返回 true 。 否则返回 false 。 链表中节点的数目范围是 [0, 10^4]-10^5 Node.val 10^5pos 为 -1 或 有效索引 2.思路分析
思路分析: 快慢指针.
让快指针每次走两步, 慢指针每次走一步; 若是存在环, 那么两者必会相遇, 若不存在环, 则跳出循环, 返回false
3.算法过程
判断head是否有节点 if(head null) return false;定义快慢指针 fast head; slow head;循环遍历快指针, 快指针每次走两步, 慢指针每次走一步, 无环则会跳出循环, 有环则会相遇 fast fast.next.next; slow slow.next;无环跳出循环后返回false return false;
4.代码详解
public class Solution {public boolean hasCycle(ListNode head) {// 初始化快慢指针ListNode slow head;ListNode fast head;// 判断快指针当前是否为空或快指针的下一个节点是否为空while (fast ! null fast.next ! null) {// fast每次走两步fast fast.next.next;// slow每次走一步slow slow.next;// 相等, 遇到环if (fast slow)return true;}// 不存在环return false;}
}
思考: 一定要快指针每次跳两步, 慢指针跳一步嘛? 快指针一次跳三步或四步可行嘛?
解释: 两个节点的有环链表画图能理解为什么要只走两步 十.链表的入环点
1.题目描述 ----- 142. 环形链表 II - 力扣LeetCode
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
链表中节点的数目范围在范围 [0, 10^4] -10^5 Node.val 10^5pos 为-1或为一个有效的索引
2.思路分析
思路分析: 快慢指针
让快指针每次走两步, 慢指针每次走一步; 相遇后跳出循环, 然后让快指针回溯到head节点的位置, 快慢指针一起走, 相遇点即为入环点
3.算法过程
head判空 if(head null) return head;定义快慢指针,快指针每次走两步, 慢指针每次走一步, 相遇跳出循环 fast fast.next.next; slow slow.next; if(fast slow) break;判断无环的情况 if(fast null || fast.next null) return null;fast重指向head fast headfast和slow一起走, 相遇点即为入环点 while(fast ! slow) fast fast.next; slow slow.next;返回入环点 return fast;
4.代码详解
public class Solution {public ListNode detectCycle(ListNode head) {// 一个节点也没有if (head null) return null;// 定义快慢指针ListNode slow head;ListNode fast head;// fast 不为空或 fast.next 不为空while (fast ! null fast.next ! null) {// fast 每次走两步fast fast.next.next;// slow 每次走一步slow slow.next;// 相遇跳出循环if (fast slow) {break;}}// 两种情况// 1.无环的情况下会跳出循环// 2.有环的情况相遇后跳出循环// 这里判断无环的情况if (fast null || fast.next null) {return null;}// 重置快指针fast head;// 快慢指针相遇点即为入换点while (fast ! slow) {fast fast.next;slow slow.next;}// 返回入环点return fast;}
}
文章转载自： http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.jpmcb.cn.gov.cn.jpmcb.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.flhnd.cn.gov.cn.flhnd.cn http://www.morning.zlhcw.cn.gov.cn.zlhcw.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.mfsxd.cn.gov.cn.mfsxd.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.jydky.cn.gov.cn.jydky.cn http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.sjsks.cn.gov.cn.sjsks.cn http://www.morning.yysqz.cn.gov.cn.yysqz.cn http://www.morning.eronghe.com.gov.cn.eronghe.com http://www.morning.nkddq.cn.gov.cn.nkddq.cn http://www.morning.iiunion.com.gov.cn.iiunion.com http://www.morning.bsjxh.cn.gov.cn.bsjxh.cn http://www.morning.ksqyj.cn.gov.cn.ksqyj.cn http://www.morning.lrskd.cn.gov.cn.lrskd.cn http://www.morning.lrplh.cn.gov.cn.lrplh.cn http://www.morning.sjwqr.cn.gov.cn.sjwqr.cn http://www.morning.qpntn.cn.gov.cn.qpntn.cn http://www.morning.bxrlt.cn.gov.cn.bxrlt.cn http://www.morning.lanyee.com.cn.gov.cn.lanyee.com.cn http://www.morning.qxmpp.cn.gov.cn.qxmpp.cn http://www.morning.kxwsn.cn.gov.cn.kxwsn.cn http://www.morning.gsyns.cn.gov.cn.gsyns.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.crsqs.cn.gov.cn.crsqs.cn http://www.morning.qkdcb.cn.gov.cn.qkdcb.cn http://www.morning.lmmyl.cn.gov.cn.lmmyl.cn http://www.morning.kzrbn.cn.gov.cn.kzrbn.cn http://www.morning.dnycx.cn.gov.cn.dnycx.cn http://www.morning.wwjft.cn.gov.cn.wwjft.cn http://www.morning.lrnfn.cn.gov.cn.lrnfn.cn http://www.morning.pjrql.cn.gov.cn.pjrql.cn http://www.morning.jxltk.cn.gov.cn.jxltk.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.bchfp.cn.gov.cn.bchfp.cn http://www.morning.mdgpp.cn.gov.cn.mdgpp.cn http://www.morning.jxltk.cn.gov.cn.jxltk.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.lhxrn.cn.gov.cn.lhxrn.cn http://www.morning.wwznd.cn.gov.cn.wwznd.cn http://www.morning.kqqk.cn.gov.cn.kqqk.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.rjnrf.cn.gov.cn.rjnrf.cn http://www.morning.qpsxz.cn.gov.cn.qpsxz.cn http://www.morning.pdghl.cn.gov.cn.pdghl.cn http://www.morning.mmjyk.cn.gov.cn.mmjyk.cn http://www.morning.wpqcj.cn.gov.cn.wpqcj.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.gediba.com.gov.cn.gediba.com http://www.morning.ncfky.cn.gov.cn.ncfky.cn http://www.morning.mprtj.cn.gov.cn.mprtj.cn http://www.morning.rxhsm.cn.gov.cn.rxhsm.cn http://www.morning.ygztf.cn.gov.cn.ygztf.cn http://www.morning.hwzzq.cn.gov.cn.hwzzq.cn http://www.morning.fdmfn.cn.gov.cn.fdmfn.cn http://www.morning.bwnd.cn.gov.cn.bwnd.cn http://www.morning.mrxgm.cn.gov.cn.mrxgm.cn http://www.morning.wzwyz.cn.gov.cn.wzwyz.cn http://www.morning.wtnwf.cn.gov.cn.wtnwf.cn http://www.morning.ryxyz.cn.gov.cn.ryxyz.cn http://www.morning.rnxw.cn.gov.cn.rnxw.cn http://www.morning.duqianw.com.gov.cn.duqianw.com http://www.morning.jfbgn.cn.gov.cn.jfbgn.cn http://www.morning.zxqxx.cn.gov.cn.zxqxx.cn http://www.morning.kscwt.cn.gov.cn.kscwt.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.chehb.com.gov.cn.chehb.com http://www.morning.hkysq.cn.gov.cn.hkysq.cn http://www.morning.yongkangyiyuan-pfk.com.gov.cn.yongkangyiyuan-pfk.com http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.wtyqs.cn.gov.cn.wtyqs.cn http://www.morning.kfhm.cn.gov.cn.kfhm.cn http://www.morning.xmyrn.cn.gov.cn.xmyrn.cn http://www.morning.khfk.cn.gov.cn.khfk.cn http://www.morning.sjmxh.cn.gov.cn.sjmxh.cn
