昆明网站建设教学视频,北京网站关键词优化,找熟人做网站的弊端,wordpress 调用分类JAVA语言编写
24. 两两交换链表中的节点
谷歌、亚马逊、字节、奥多比、百度
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。…JAVA语言编写
24. 两两交换链表中的节点
谷歌、亚马逊、字节、奥多比、百度
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
教程https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频https://www.bilibili.com/video/BV1YT411g7br
方法一双指针法
思路 操作之后的链表 复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
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) {ListNode dumyhead new ListNode(-1); // 设置一个虚拟头结点dumyhead.next head; // 将虚拟头结点指向head这样方面后面做删除操作ListNode cur dumyhead;ListNode temp; // 临时节点保存两个节点后面的节点ListNode firstnode; // 临时节点保存两个节点之中的第一个节点ListNode secondnode; // 临时节点保存两个节点之中的第二个节点while (cur.next ! null cur.next.next ! null) {temp cur.next.next.next;firstnode cur.next;secondnode cur.next.next;cur.next secondnode; // 步骤一secondnode.next firstnode; // 步骤二firstnode.next temp; // 步骤三cur firstnode; // cur移动准备下一轮交换}return dumyhead.next;}
}19. 删除链表的倒数第 N 个结点
字节跳动、亚马逊、Facebook
给你一个链表删除链表的倒数第 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]提示
链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz
**进阶**你能尝试使用一趟扫描实现吗
教程https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
视频https://www.bilibili.com/video/BV1vW4y1U7Gf
方法一自己写的
思路很简单的方法首先写一个循环遍历head获得当前val的个数size。根据倒数第n个数、与size及正着数的索引的关系flagsize-n1删除结点。对于特殊情况head为null则返回空。若删除是头结点也就是nsize的时候直接返回head.next。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {
if (headnull) return null;int size0;ListNode cur head;ListNode temphead;ListNode pre new ListNode(0,temp);while(cur!null){cur cur.next;size;//计算当前ListNode的个数}if(nsize) return head.next;//如果是删第一个的话就返回head.nextint flag0;//记录索引位置while(temp!null){//temp是遍历的if(flagsize-n){//size-n是正数的索引前一个pre.nexttemp.next;//删除操作}flag;temptemp.next;prepre.next;}return head;}
}160. 相交链表
字节跳动
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
图示两个链表在节点 c1 开始相交**** 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,0,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8
解释相交节点的值为 8 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,0,1,8,4,5]。
在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。示例 2 输入intersectVal 2, listA [0,9,1,2,4], listB [3,2,4], skipA 3, skipB 1
输出Intersected at 2
解释相交节点的值为 2 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [0,9,1,2,4]链表 B 为 [3,2,4]。
在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2
输出null
解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。
由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。
这两个链表不相交因此返回 null 。提示
listA 中节点数目为 mlistB 中节点数目为 n0 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA 1] listB[skipB 1]
**进阶**你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案
教程https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
方法一
思路求出两个链表的长度并求出两个链表长度的差值然后让curA移动到和curB 末尾对齐的位置比较curA和curB是否相同如果不相同同时向后移动curA和curB如果遇到curA curB则找到交点。否则循环退出返回空指针。
复杂度分析
时间复杂度 O ( n A n B ) O(nAnB) O(nAnB),nA是链表A的长度,nB是链表B的长度空间复杂度 O ( 1 ) O(1) O(1)
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA headA;ListNode curB headB;int lenA 0, lenB 0;while (curA ! null) { // 求链表A的长度lenA;curA curA.next;}while (curB ! null) { // 求链表B的长度lenB;curB curB.next;}curA headA;curB headB;// 让curA为最长链表的头lenA为其长度if (lenB lenA) {//1. swap (lenA, lenB);int tmpLen lenA;lenA lenB;lenB tmpLen;//2. swap (curA, curB);ListNode tmpNode curA;curA curB;curB tmpNode;}// 求长度差int gap lenA - lenB;// 让curA和curB在同一起点上末尾位置对齐while (gap-- 0) {curA curA.next;}// 遍历curA 和 curB遇到相同则直接返回while (curA ! null) {if (curA curB) {return curA;}curA curA.next;curB curB.next;}return null;}}142. 环形链表 II
字节跳动、谷歌 Google、Facebook
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示
链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引
**进阶**你是否可以使用 O(1) 空间解决此题
教程https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频https://www.bilibili.com/video/BV1if4y1d7ob/
方法一
思路可以使用快慢指针法分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {// 有环ListNode index1 fast;ListNode index2 head;// 两个指针从头结点和相遇结点各走一步直到相遇相遇点即为环入口while (index1 ! index2) {index1 index1.next;index2 index2.next;}return index1;}}return null;}
}
