上海网站网络科技有限公司,企业服务类型有哪些,基层建设期刊在哪个网站上检索,网页设计手机软件24. 两两交换链表中的节点
题目描述
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。 做题思路
可以设置虚拟头结点cur和画图…24. 两两交换链表中的节点
题目描述
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 做题思路
可以设置虚拟头结点cur和画图来方便理清逻辑。
参考代码
class Solution {public ListNode swapPairs(ListNode head) {ListNode vnew ListNode(0);//虚拟头结点v.nexthead;//虚拟头结点指向头结点ListNode curv;while(cur.next!nullcur.next.next!null){//提前保存节点ListNode tmpcur.next;ListNode tmp1cur.next.next.next;cur.nextcur.next.next;//步骤一cur.next.nexttmp;//步骤二cur.next.next.nexttmp1;//步骤三curcur.next.next;//cur前进进行下一轮}return v.next;}
}19. 删除链表的倒数第 N 个结点
题目描述
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 做题思路
本题可以使用双指针法快指针首先前进n次随后快慢指针一起前进当快指针到达末尾时慢指针到达目标节点的前一个节点。
就拿上图举例快指针前进2次随后快慢指针一起前进当快指针到达5慢指针到达3.
参考代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode vnew ListNode(0);//虚拟头结点v.nexthead;ListNode fastv;//快指针ListNode slowv;//慢指针for(;n0;n--)fastfast.next;//快指针首先前进n次while(fast.next!null){//慢指针一起前进fastfast.next;slowslow.next;}slow.nextslow.next.next;//删除节点return v.next;}
}面试题 02.07. 链表相交
题目描述
给你两个单链表的头节点 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]
做题思路
本题的关键在于如何让两个指针不会错开例如一个指针已经到公共链表另一个还没到这样就无法判断了。
因此可以利用两个链表的长度差让两个指针初始位置在公共节点前的相同位置链表A长就先移动指针a链表B长就先移动指针b。
参考代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode aheadA;ListNode bheadB;int lena0;int lenb0;//获取链表长度while(a!null){aa.next;lena;}while(b!null){bb.next;lenb;}aheadA;bheadB;//移动指针使两者位于相同初始位置if(lenalenb)for(int i0;ilena-lenb;i)aa.next;else for(int i0;ilenb-lena;i)bb.next;//移动指针使其指向公共节点while(a!null){if(ab)return a;aa.next;bb.next;}return null;}
}142. 环形链表 II
题目描述
给定一个链表的头节点 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 或者链表中的一个有效索引
做题思路
本题可使用双指针法若链表内存在环则快慢指针一定会相遇。相遇后再从头结点出发一个慢指针则该指针将与原先的慢指针相遇。
参考代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){//判断是否有环fastfast.next.next;//快指针移动slowslow.next;//慢指针移动if(slowfast){//有环fasthead;//从头结点出发一个慢指针(快指针重复利用)while(true){if(slowfast)return slow;//相遇slowslow.next;//原先的慢指针fastfast.next;//新设的慢指针}}}return null;}
}
