逆转链表是简单而又简单的链表问题,其问题的方法之一可以设置三个指针,一个指向当前结点,一个指向前驱结点,一个指向后继指针代码如下:class Solution { public:ListNode* ReverseList(ListNode* pHead) { // if(pHead==NULL || pHead->next==NULL) // return pHead;ListNode *cur=pHead;ListNode *pre=NULL;ListNode *tmp;while(cur){tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return pre;} };原文：http://www....
给定链表的表头节点head,实现删除链表的中间节点的函数 推展： 给定链表的头节点，整数a 和 整数 b,实现删除a/b处节点的函数 先来分析原问题， 长度1 直接返回 长度2 将头节点删除 长度3 删除第二个 长度4 删除第二个 长度5 删除第三个。。。。。。长度每增加2 删除的节点就向后移动一个节点如果要删除一个节点，则需要找到待删除节点的前一个节点package TT;public class Test87 {public class Node{public int value;public N...
很容易想到递归，实现确实不是太容易，对本人来说。平衡二叉树是有序的，要求链表也是有序。\代码：#include<iostream> //平衡二叉树转化为双向链表 using namespace std;typedef struct tree{int data;struct tree *lchild;struct tree *rchild; }Tree,*pTree;void createBST(pTree &pHead){int temp;scanf("%d",&temp);if(temp){pHead = new Tree();pHead->data = temp;createBST(pHead->lchild);createBST(pHead->rchild);}el...
题目链接：https://www.acwing.com/problem/content/149/题目中给出一些点在x轴上的位置，问选出k对位置的情况下，他们的两两距离之和的最小值是多少？容易直到，选中的位置一定是相邻的而且没有交集，我们对原始序列求差分之后问题就变成了在这个差分序列中寻找k个不相邻的数，使得和最小。当选中了其中的k个两两间隔为1的位置之后，如果下一次从剩下的区间里面选出一个最小的区间跟这k个点相邻就破坏了性质，这k个点一定会被周围...
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 核心代码： public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); Stack<Integer> stack = new Stack<>(); while (listNode != null) { stack.push(listNode.val); //入栈 listNode = listNode.next;//往后移动 } whil...
一：问题已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1，否则，只返回0。注意：这里的链表中没有给出链表长度哟二：思路设置两个指针p、q，分别指向该链表的第一个元素（头结点的下一个元素）和头结点，一个整数num（初值为1），p向后移动一...
【本文谢绝转载】《大纲》数据结构：起源：基本概念数据结构指数据对象中数据元素之间的关系 逻辑结构物理结构数据的运算算法概念：概念算法和数据结构区别算法特性算法效率的度量大O表示法时间复杂度案例空间复杂度时间换空间案例 1)线性表：线性表初步认识：线性表顺序结构案例线性表顺序结构案例，单文件版线性表的优缺点企业级线性表链式存储案例：C语言实现企业级线性表链式存储案例：C语言实现 单文件版企业级线性表链式存...
前言：前面几篇介绍了线性表的顺序和链式存储结构，其中链式存储结构为单向链表（即一个方向的有限长度、不循环的链表），对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说只能向后走，如果走过了，就回不去了，还得重头开始遍历，所以就衍生出了循环链表一、简介 定义：将单链表中中断结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾详解的单链表称为单循环...
一。题目要求：输入一棵二叉排序树，现在要将该二叉排序树转换成一个有序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。 #include<stdio.h> #include<stdlib.h>typedef struct node {int nValue;struct node *pLeft;struct node *pRight; }BinaryTree;void AddNode(BinaryTree **pTree,int nNum) {BinaryTree *pTemp = NULL;pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));pTemp...
什么也不说, 直接上代码: 功能点有: 1, 获取尾结点 2, 添加(添加节点到链表的最后面) 3, 添加(根据节点的no(排名)的大小, 有序添加) 4, 单向链表的 遍历 5, 链表的长度 6, 删除某一个节点 7, 更换指定位置的节点 8, 查询第n个节点 9, 查询倒数第n个节点 10, 链表反转, 使用递归实现 11, 逆序打印 12, 合并二个有序链表, 且结果仍然是有序的//英雄节点 class HeroNodeLv{public int no;//英雄排名public String name;//名字public S...
方法一： 1 #include <iostream>//创建二叉树，要用二级指针2 3usingnamespace std;4 5 typedef struct TreeNode6{7char data;8struct TreeNode *left;9struct TreeNode *right; 10}BiTree; 1112void creatBitree(BiTree **T) 13{ 14char ch; 15 cin >> ch; 16if (ch == ‘#‘) 17 { 18 *T = NULL; 19 } 20else21 { 22 *T = (BiTree*)malloc(sizeof(TreeNode)); 23 (*T)->data = ch; 24 ...
链表（Linked List）是不同于数组的另一种数据结构，它的存储单元（即结点或元素）除了包含任意类型的数据之外，还需要包含指向另一个结点的引用，后文会用术语链接表示对结点的引用。 下面会列出链表与数组的具体不同： （1）数组需要一块连续的内存空间来存储；而链表则恰恰相反，通过指针将零散的内存串联在一起。 （2）数组在插入和删除时，会做数据搬移，其时间复杂度是 O(n)；而链表只需考虑相邻结点的指针变化，因...
题目：给定两个已排序的链表，返回合并后的链表。 思路：将链表L2的每个结点插入到链表L1中，时间复杂度为O(m+n)，m、n分别为两条链表的长度。 代码： 1struct ListNode2{3int value;4 ListNode *next;5 ListNode(int v): value(v), next(NULL)6 {7 }8};910 ListNode *mergeSortedList(ListNode *L1, ListNode *L2) 11{ 12 ListNode dummy(-1), *p1 = &dummy, *p2 = L2; //L1的辅助头结点dummy，因为可能在头部...
1、常用缓存策略 缓存淘汰策略：指的是当缓存被用满时清理数据的优先顺序。 缓存是一种提高数据读取性能的技术，比如常见的cpu缓存、数据库缓存、浏览器缓存。但是缓存的大小有限，当缓存用满的时候，哪些数据应该被清理出去，哪些数据应该被保留？ 解决方案：FIFO（First In，First Out）--->先进先出策略 LFU（Least Frequently Used）---> 最少使用策略 LRU（Least Recently Used）--->最近最少使用策略 2、数组和链表底...
一、什么是链表和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。二、链表的优劣插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。 和数组相比，内存空间消...