Razertory 的技术博客

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 1boolean VerifySquenceOfBST(int [] sequence) BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，... 続きを読む…

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 1boolean HasSubtree(TreeNode root1,TreeNode root2) 首先在 A 中找到一个节点，满足这个节点是 B 的 root 节点，在此基础上按照 B 的结构遍历 A，B。 12345678910111213141516171819202122boolean H... 続きを読む…

Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed. 1ListNode swapPairs(ListNode head) 由于要交换... 続きを読む…

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and retur... 続きを読む…

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 传送门 定义一个 dummy 节点，pre，cur 节点。比较 pre.next 和 cur。如果相同让 pre = pre.next 做删除操作 12345678910... 続きを読む…

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 传送门 定义一个慢和一个快指针，当两个指针相遇的时候。快指针速度和慢指针一致，等再次相遇的时候这个点就是环入口。 1234567891011121314151617ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHea... 続きを読む…

输入两个链表，找出它们的第一个公共结点。 传送门 首先计算出两个链表的各自长度，然后计算出一个差值 delta。然后基于 delta 的值走对应的节点，当 delta 变为 0 的时候停止。并判断是否有公共节点 12345678910111213141516171819202122232425ListNode FindFirstCommonNode(ListNode pHead1, Lis... 続きを読む…

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） 传送门 每个链表都有两个指针，这种情况下最简单的做法是用一个 k, v 的方式存放所有的节点以及新的只有 label，指针指向的节点为空的节点。然后用原来的节点指针指向的值复... 続きを読む…

输入一个链表，反转链表后，输出新链表的表头。Example: 12Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULL 传送门 反转的过程需要提前准备好下个节点的，用到两个指针，cur 和 pre 指向新节点和用于存放原本的下个节点 12345678910ListNode r... 続きを読む…

归并排序最核心的思想就是 merge 两个有序的数组。假设两个只有一个元素的数组合并，比如 [34], [33]，合并之后就是 [33, 34]。假设这个数组要和 [1, 100] 合并，合并之后就是 [1, 33, 34, 100]。 可以看出当大小为 n 的有序数组和大小为 m 的有序数组合并之后大小就是 n + m。所以最重要的就是写出高效的合并算法，假设函数的签名是 123// a... 続きを読む…