代码随想录算法训练营第4天 | 题目 24. 两两交换链表中的节点 、 19.删除链表的倒数第N个节点 、 142.环形链表II

代码随想录算法训练营第4天 | 题目 24. 两两交换链表中的节点 、 19.删除链表的倒数第N个节点 、 142.环形链表II

文章来源:代码随想录

题目名称: 24. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
在这里插入图片描述

第一想法:

首先是加入虚拟头节点,两两交换,则要针对奇数和偶数的情况进行讨论。交换时需要补充中间点位来记住下一个点位的顺序。

解答思路:

初始时,cur指向虚拟头结点,然后进行如下三步:
在这里插入图片描述
操作后为:
在这里插入图片描述
要注意:在移动cur时,需要保存其他的节点。反转的操作是cur的后两个节点。

换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序

困难:

理清关系需要画图,画图后能明白之间的关系,也能明确循环进行的限制。

收获:

画图法是处理链表的好方法,可以使得抽象的链表具象化。

题目名称: 19.删除链表的倒数第N个节点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
在这里插入图片描述

19.删除链表的倒数第N个节点
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2:
输入:head = [1], n = 1 输出:[] 示例 3:
输入:head = [1,2], n = 1 输出:[1

第一想法:

先遍历到最后,计算size,再通过size-n-1寻找去除节点之前的节点吗,但是是两次循环。

解答思路:

同样使用双指针,做到一次遍历,设计快指针为慢指针的n+1位置,直到快指针指向null。
同样添加虚拟指针。

困难:无

双指针法的设计是减少遍历次数的方法

收获:

双指针法的设计是减少遍历次数的方法

题目名称:面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:
在这里插入图片描述
在这里插入图片描述

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

第一想法:

首先确定,不是值相同时是交点,而是链表指针指向同一位置是焦点,能否分别移动AB是得他们相等时,则得到?

解答思路:

简单来说,就是求两个链表交点节点的指针。 这里同学们要注意,交点不是数值相等,而是指针相等。

为了方便举例,假设节点元素数值相等,则节点指针相等。

看如下两个链表,目前curA指向链表A的头结点,curB指向链表B的头结点:
在这里插入图片描述
我们求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB 末尾对齐的位置,如图:
在这里插入图片描述
此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点。

否则循环退出返回空指针。

困难:

给出的方法通俗易懂,可以知道长链表的之前几位没有交点的可能。有第二个解法:

(版本二) 合并链表实现同步移动
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		// p1 指向 A 链表头结点,p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步,如果走到 A 链表末尾,转到 B 链表
			if (p1 == null) p1 = headB;
			else            p1 = p1.next;
			// p2 走一步,如果走到 B 链表末尾,转到 A 链表
			if (p2 == null) p2 = headA;
			else            p2 = p2.next;
		}
		return p1;
    }
}

比较抽象,两个链表指针交叉,则两个指针搜索的距离总能使得最后指向一个节点。

收获:

画图能更直观的看出找寻的规律

题目名称:142.环形链表II

题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。
在这里插入图片描述

第一想法:

环形链表的判断应该是双指针,快慢指针都进入环中,当两个指针相等是则有环,两个指针之间的距离是环的大小。如何寻找链表的入口,和是否有环?

解答思路:

具体解答思路参照:代码随想录142

困难:

如何确定快慢指针在环中一定会相遇,如果slow每次移动一位,快指针一次移动两位,fast相对slow每次移动一位,一定可以追上。
而如何确定环的入口
在这里插入图片描述
突破口在fast走的距离等于slow的两倍,2*(x+y)=n(y+z)+x+y
最后化为:x = (n - 1) (y + z) + z
这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。
让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。

收获:

处理环状问题画图是重要的技巧,通过画图验算实现。

相关推荐

最近更新

  1. 05-5.4.3 树和森林的遍历

    2024-06-09 17:06:02       0 阅读
  2. k8s核心组件

    2024-06-09 17:06:02       0 阅读
  3. LeetCode 58. 最后一个单词的长度

    2024-06-09 17:06:02       0 阅读
  4. 关于lspci命令的相关使用

    2024-06-09 17:06:02       0 阅读

热门阅读

  1. Django中drf动态过滤查询

    2024-06-09 17:06:02       8 阅读
  2. 006 RabbitMQ

    2024-06-09 17:06:02       6 阅读
  3. 记录一次jlink连不上cpu的情况

    2024-06-09 17:06:02       8 阅读
  4. wordpress网站建设详细过程

    2024-06-09 17:06:02       6 阅读
  5. 移动端前端开发遇到过的Andorid和IOS的差异记录

    2024-06-09 17:06:02       5 阅读
  6. Audio音频资源播放

    2024-06-09 17:06:02       5 阅读
  7. springboot + easyRules 搭建规则引擎服务

    2024-06-09 17:06:02       6 阅读
  8. AI学习的基础理论路径

    2024-06-09 17:06:02       4 阅读
  9. es6 proxy的作用和用法

    2024-06-09 17:06:02       5 阅读
  10. 简单记录个python国内镜像源

    2024-06-09 17:06:02       5 阅读