基于双向链表和hashmap的LRU算法实现 什么是LRU LRU缓存淘汰算法就是一种常用策略。LRU的全称是Least Recently Used，也就是说我们认为最近使用过的数据应该是有用的，很久都没用过的数据应该是无用的，缓存满了就优先删除那些很久没有用过的数据。代码 #include<iostream> #include<string> #include<map> #include<vector> #include<stack> using namespace std; struct Node {int data;int key;Node *nextNode;Node *beforeNode...
目录Remove Duplicates from Sorted List删除排序链表中的重复元素 Remove Duplicates from Sorted List删除排序链表中的重复元素 Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次 输入: 1->1->2 输出: 1->2输入: 1->1->2->3->3 输出: 1->2->3/*** Definition f...
题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 我的思路：因为对java链表不太熟悉，所以我直接查看了题解。 方法一：迭代法：目前已知最优解，时间O（n），空间O（1）。 先设置一个前置指针prev，指向前面一个结点（第一个prev指向null）， 创建一个next指针记录下当前结点curr的next结点，将当前结点curr的next指针指向prev结点，然后就让当前结点curr的下一个结点（先用next记录）成为当前结...
LeetCode全集请参考：LeetCode Github 大全 题目 24.两两交换链表中的节点https://leetcode-cn.com/problems/swap-nodes-in-pairs/ /** @lc app=leetcode.cn id=24 lang=java** [24] 两两交换链表中的节点*/// @lc code=start /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNo...
转： 算法入门题：如何反转一个单向链表？ 最近在 LeetCode 上面玩 链表 类型的题目，所以打算写一篇文章，分享一下在做链表类型题目的心得。 众所周知，玩链表就是玩指针，今天跟大家讲解一个链表的入门题目，如何反转一个单向链表 也是 LeetCode #206 是很热门的一道编程题 LC#206 Reverse Linked List ，如图：解题理论： 想要反转一个单向链表，除了当前的 head 指针外，我们还另外需要两个辅助指针：preNode 用于保存上一个引...
主要完成了三道单链表的算法题和学习了双链表的概念及其增删改查1、删除单链表中的重复的元素。如1-2-3-3-4-4 输出为1-2思想：这种算法题就是遍历链表将重复的数字删除就行，定义指针n1，n2，n3，n2和n3为移动的指针，主要比较相连的数据是否相同，也就是确定相同数据的个数，n1作为n2的前一个节点，n1->next=n3;直接将n2与n3之间的元素删除，当n3为空时，遍历也就结束。但是此题需要注意：当前几个节点相同时，这时候需要改变头结...
题目描述 给定一个链表，请判断该链表是否为回文结构。 示例1 输入 [1,2,2,1] 返回值 true 思路: 双指针，快指针一次走两步，慢指针一次走一步，快指针走完，慢指针走到中点。然后将中点开始后面节点逆序，比较完之后再将还原该链表。 例如：1->3->5->3->1，慢指针会到达5处，然后右半部分逆序，将5的next指向null，将后面3的next指向5，将1的next指向3，得到1->3->5<3<1，一个节点从head开始遍历，一个节点从尾节点开始遍历...
今天还是继续刷单链表的相关算法题1、链表分割：就是将一个链表的值按照小于x或者大于等于x排序，但不改变相对位置。如链表1-3-5-2-6-7-4.x==4排序后的单链表应该为1-3-2-5-6-7-4；思想：定义2个头结点lesshead,greathead,并且需要2个尾节点lesstail,greattail;这个方面需要注意一点就是头结点的定义不是和指针定义一样，节点的定义需要malloc申请，listnode lesshead=(listnode)malloc(sizeof(listnode));第二步需要定义一个cur指...
今天主要完成了链表的5道算法题，不得不说leedcode和牛客网真是个好东西，点个赞。1、反转链表，如1->2->3->4->NULL,反过来打印。思想：第一种可以利用单链表的头插法来实现，定义一个新节点newnode，依次将1、2、3、4插到newnode,但是插完之后需要将newnode重新赋值到第一个节点。第二种来利用迭代思想，定义n1,n2,n3分别为NULL，头节点head，头结点的下一位head->next，n2->next=n1;ni=n2;n2=n3;这样可以将链表指针反向指过来。2...
编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。public class JosephusProblem {public static void main(String[] args) {int n = 5;int m = 2;solution(n, m);}private static void solution(int n, int m) {if(n < 1 || m < 1){System.out.println("The number of Sold...
题目 在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。 要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。 分析 首先要判断这两个单链表是否有环。因为有环的情况下需要单独讨论。若两个链表都没环，有可能相交也有可能不...
目录 1、数组 2、链表 最简单是数据结构就是线性表，包括数组、链表、栈和队列。线性表就是数据像线一样连城一条线，线上的每个节点都只有前后两个方向。其他的就是非线性结构，包括树（一个节点可以链接到多个节点）、图（节点可能成环），或者散列表、跳表等。用一个对比图展示： 1、数组 数组的特点： 1）、属于线性表 2）、数组创建时会申请一片连续的内存空间，并且存储每个位置上的数据类型相同（即...
1. 链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个或两个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为节点（node）。 2.链表的第一个节点和最后一个节点，分别称为链表的头节点和尾节点。尾节点的特征是其 next 引用为空（null）。链表中每个节点的 next 引用都相当于一个指针，指向另一个节点，借助这些 next 引用，我们可...
现有一个链表（可能有环） 现在要把它逆序输出出来，可能存在链表循环，这个是要注意的地方 以下代码模拟一个循环链表的逆序操作。 思路是，还是按照单链表的逆序思路来进行，只不过每一次循环，都需要判断，未逆序节点是否指向已逆序的节点，如果是，break，如果不是，则继续。 #include <iostream> using namespace std; struct Node {int value;Node* next; }; int main(void) {Node* node1 = new Node;node1->value = 1;Node* ...
题目 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点， 而C表中的结点为A表中值大于零的结点。（链表A中的元素为非零整数，要求B、C表利用A表的结点。） 解答 链表B使用链表A的头结点，链表C申请一个新的头结点。对链表A进行遍历的同时进行拆解，可以使用前插法或者后插法。 /* 设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值...