《剑指offer》-链表找环入口
题目描述 一个链表中包含环，请找出该链表的环的入口结点。 初步想法是每个节点做几个标记，表示是否被访问过，那么遍历链表的时候就知道哪个被访问到了。但是不会实现。 另一个直觉是判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。 容易知道，当1x的指针p1和2x的指针p2相遇时，p1走了x步，p2走了2x步，而p2比p1多走的，有两部分：(1)环内部，p1还没有走过....
《剑指offer》-链表的第一个公共节点
题目描述 输入两个链表，找出它们的第一个公共结点。 这题目是指针相关的题目。初步要判断出来，有公共节点的两个指针，应当是链表后半部分相同。这样的话，当遇到第一个相同节点（不是node的val相同，而是node完全相同），则找到了结果。 网上找到一种很简介的写法。稍微分析了下，其实就是将两个链表L1和L2进行了拼接，得到L1+L2和L2+L1两个拼接结果。这两个长度相同，那么one node by....
剑指offer 面试题5—从尾到头打印链表
题目： 输入一个链表的头结点，从尾到头反过来打印出每个结点的值。 考虑用栈 public void invertedList1(ListNode head) { if (head == null) { return; } ListNode p = head; Stack<Integer>...
剑指offer系列之五十九：链表中环的入口节点
题目描述 一个链表中包含环，请找出该链表的环的入口结点。 此题的思路其实 很简单，之所以出现环，是因为在整个链表中出现了重复的节点，而遇到的第一个重复的节点就是环的入口节点。所以可以使用Set来保存遍历到的节点，因为Set集合是不允许出现重复元素的，所以当一个节点被第二次添加的时候，往Set中放元素是失败的。所以可以利用这一点找出第一个重复的元素。基于这种思路的代码比较简洁，代码如下（已被牛...
剑指offer系列之五十八：删除链表中重复的节点
题目描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 因为需要找到重复的节点，所以对链表进行遍历，而且在遍历的过程中需要对每个当前遍历的节点以及后面的节点进行比较直到遇到下一个节点不与当前节点重复。如果下一个节点与当...
剑指offer系列之三十五：两个链表的第一个公共节点
题目描述 输入两个链表，找出它们的第一个公共结点。 由于是单链表，所以可以发现从第一个公共节点开始，后面的结点都是相同的，一种思路是从两个链表的尾部开始遍历，直到发现最后一个相同的结点为止，那么这最后一个相同的结点是单链表的角度看就是两个链表的第一个公共节点了。还有一种思路是不需要从尾部开始遍历，毕竟从尾部遍历单链表的话还得使用反转链表的方法进行操作，首先计算出两个链表的长度，让更长的那个单...
剑指offer系列之二十五：二叉搜索树与双向链表
题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 由于二叉搜索树的中序遍历就是排序的，如果是构造单链表，只需要一次中序遍历就可以了，但现在需要构造双链表，也就是在中序遍历的过程中需要设置每个节点的left与right指针，现在问题是如何设置这两个指针？二叉搜索树有一个特点，就是根节点的左子树上所有节点都比根节点的值小...
剑指offer系列之二十四：复杂链表的复制
题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。 下面是我第一想到的思路：因为next指针是固定的，在复制的时候这点比较好处理，由于特殊指针是任意的，可能是在节点之前，也可能在节点之后，所以必须解决这个棘手问题。不管至少，可以从链表的第一个节点开始遍历，直到该特殊指针指向的节点，并设置该节点的特殊指针。还有一种思路（也是书上...
剑指offer系列之十五：合并两个排序的链表
题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 这道题我的第一思路这样的：可以先遍历这两个排序的链表，把遍历的结果存放在一个集合中，然后调用库函数Arrays.sort方法完成排序，之后，根据这些排好序的结果重新创建一个链表，即为合并之后但仍然排序的链表。但是这种思路需要额外的List和创建链表的空间开销，而且时间复杂度最快也是O(nl...
剑指offer系列之十四：反转链表
题目描述 输入一个链表，反转链表后，输出链表的所有元素。 思路如下：在遍历链表上的每个节点的时候，就修改其指针，当遍历到最后一个结点的时候，整个链表就反转完成了。所以需要创建三个变量：一个是当前遍历的结点，一个是遍历结点的前一个结点，还有一个是当前遍历结点的下一个结点。基于这种思路可以写出如下的实现代码（已被牛客AC）： package com.rhwayfun.offer; publ...
本页面内关键词为智能算法引擎基于机器学习所生成，如有任何问题，可在页面下方点击"联系我们"与我们沟通。
数据库
分享数据库前沿，解构实战干货，推动数据库技术变革
+关注