Problem：【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。 实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot的节点， 中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。 除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5->1，pivot = 3。 调整后链表可以是1->0->4->9->5， 可以是0->1->9->5->4。 总之， 满足左部分都是小于3的节点， 中间部...
【题目】据说著名犹太历史学家Josephus有过以下故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，报数到3的人就自杀，然后再由下一个人重新报1，报数到3的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结...
链表（Linked List）的经典使用场景，LRU缓存淘汰算法 缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如：CPU缓存、数据库缓存、浏览器缓存等等 缓存的大小有限，用满时 留哪些 删哪些呢？先进先出策略FIFO（First IN，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used） 举例：买了很多书，书太多了放不下，作大扫除，选择去掉一部分策略如...
1. 问题 : 链表的整体反转 题目 : 将链表整体进行反转 例如 : 链表 1 --> 2 --> 3 --> 4 --> 5 反转为 5 --> 4 --> 3 --> 2 --> 1 //算法思想 : 记录 当前遍历结点的前一个结点和后一个结点 确保每次向后遍历能够找到 //当前结点的前一个结点 以此完成链表的反转 同时时间复杂度最小 为O(n) listNode * listReverse_all(listNode * list) {listNode * nextNode = list->next; listNode * rNode = list;listNode * beforeNode = NUL...
Problem: 反转单向和双向链表 【题目】 分别实现反转单向链表和反转双向链表的函数。 【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间 复杂度要求为O(1) Solution: 学会使用指针 1 #pragma once2 3 #include <iostream>4 5 using namespace std;6 7 struct Node8 {9 int val;10 Node* next;11 Node(int a = 0) :val(a), next(NULL) {}12 };13 14 void ReverSingleList(Node*& head)//反转单向链表15 {16 ...
【题目】分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。【要求】如果链表长度为N，时间复杂度达到O（N），额外空间复杂度达到O（1）。【题解】从头遍历链表，每移动一次，K--，直至移动到链表尾部，此时k>0,说明k太大，链表不用删除k==0，链表长度即是k， 删除头结点即可k<0,再次重头遍历链表，每移动一次，k++,当k==0时，此时结点为要删除结点的前结点，使其指向下一个结点即可双向...
题目 已知一个带有表头结点的单链表，结点结构为data link在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第kkk个位置上的结点。若查找成功，算法输出该结点的data域的值，并返回111，否则，只返回000。 分析 解决这个题目的方法有很多种：采用两遍或多遍扫描链表，先得到链表长度，再顺序扫描到L?KL-KL?K位置； 采用递归算法，在递归返回位置计数，计到kkk位置； 辅助数组；但上述这些方法都不是最优的，我们可以...
数据结构与算法之反转单向链表和双向链表目录反转单向链表和双向链表1. 反转单向链表和双向链表题目描述代码实现public class Code_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node reverseList(Node head) {Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return...
问题起源: 漫画算法:如何判断链表有环? 针对寻找入环点,网络上提供的算法为: 设指针p,p从head出发,速度与慢指针相同,慢指针从相遇点同时出发,到两个指针相遇时的结点,即为入环点. 这里给出该方法正确的证明:
链表分类单向链表 双向链表 优势:删除某个节点更加高效, 可以快速找到前驱节点 可以方便的在某个节点前插入元素循环链表 当要处理的数据具有环形结构的时候, 适合循环链表. 如约瑟夫环问题 双向循环链表数组的缺点是大小固定, 一旦声明长度就要占用连续的内存空间, 当空间不够用时更换更大的空间, 此时就需要将原数组的所有数据迁移过去, 比较费时. 链表则可以动态扩容. 数组在查询上可以更快, 链表在插入和删除上更快, 为了结合数...
题意 给定一个无序单链表的头节点head，实现单链表的选择排序。 题解按选择排序方法：每次从原链表找出最小值，从原链表删除，插入新的有序链表。 时间复杂度O(n^2) 额外空间复杂度O(1)代码 public class Main {public static void main(String args[]) {Node n1=new Node(2);Node n2=new Node(1);Node n3=new Node(3);n1.next=n2;n2.next=n3;Node head=n1;Node sortHead=selectSort(head);Node pNode=sortHead;while(pNode!=null)...
TWO POINTER 快指针速度2 ， 慢指针速度1 相对速度1，有环必然相遇public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head,slow = head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;if(slow == fast){return true;}}return false;} }
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链。链表分为单链表、双链表、循环链表。 一、单链表插入：链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点(前驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点（见下图）。由上图可知，B、C之间插入D，三者之间的关系为current为插入节点的前驱节点 current->next = new? ? ? ? ?...
136. 邻值查找 给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求： min 1≤j<i |Ai?Aj| 以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj较小的那个。 输入格式 第一行输入整数n，代表序列长度。 第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。 输出格式 输出共n-1行，每行输出两个整数，数值之间用空格隔开。 分别表示当i取2~n时，对应的min1≤j<i|Ai?Aj|和Pi的...
最近在学习java，但是对于数据操作那部分还是不熟悉 因此决定找几个简单的算法写，用php和java分别实现 1.合并两个有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 java/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }*...