一.单链表 单链表： 在逻辑上是连续的，在物理存储上是不连续的（每一个数据元素都占一个单独 的位置）， 只能够从头到尾遍历。1、单链表的结构申明typedef int ElemType; typedef struct Node {ElemType data; // 元素struct Node *next; // 下一个结点的地址 }SNode, *LinkList; 12、带头结点的单链表? 1 typedef int ElemType;2 typedef struct Node3 {4 union5 {6 int length;7 ElemType data;8 };9 struct Node *next; ...
题目描述 有 \(n\) 个物品，每个物品有两个属性：权值 \(v\) 和大小 \(s\)。 你要选出 \(m\) 个物品，使得你选出的物品的权值的和的 \(d_v\) 减掉大小的极差的 \(d_s\) 次方最大。\(n\leq 200000,m\leq 50,1\leq d_v,d_s\leq 2\)题解 如果选的物品的数量不到 \(m\) 个，且不连续，那么一定不是最优的。 因为如果不是连续的，那么可以多选一个大小在这些物品之间的物品，使答案更优。 如果选了 \(m\) 个物品，那么可...
这题有两种思考方式，一种是添加辅助空间，先进后出，当然是栈了，做法就是遍历链表，将值压入栈中，然后再一次弹出。还有一种方法是链表反序，链表反序也有两种方法。一种是将链表在原有的基础上更改指针，进行反序。光看代码可能不太还理解，我们可以看一下执行过程。假设p1->p2->p3->p4->p5->p5->.......那么执行一次为p1<-p2->p3->p4->p5.......然后p1=p2;p2=p3;将其更新为新的p1->p2->p3->p4....循环执行，直到p1->p2->p3.......
/*** 单向环形链表应用 -- 约瑟夫环* Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，* 数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，* 由此产生一个出队编号的序列。*/ public class Josepfu {public static void main(String[] args){CircleSingleLinkedList linkedList = new CircleSingleLinkedList();linkedList.add(5)...
具体分析可见http://blog.csdn.net/libin1105/article/details/48267113需要指出的是，上述博客中2*(a+b)=a+b+c+b应该改为2*(a+b)=a+b+(c+b)*n，其中n为自然数。然后得到关系式a=(b+c)*n-b由此可见两个指针会相遇在环的入口。 1class Solution {2public:3 ListNode* EntryNodeOfLoop(ListNode* pHead)4 {5if(pHead==NULL||pHead->next==NULL)6return NULL;7 ListNode* one=pHead;8 ListNode* two=pHead;9do...
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。 现有一个链表 – head = [4,5,1,9]，它可以表示为: 示例 1： 输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2： 输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：给定你链表中值为 1 的第三个节点，那么在调用了...
86. 分隔链表https://leetcode-cn.com/problems/partition-list/难度完成日期耗时提交次数中等2020-1-160.5小时1问题描述给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5解题思路普通方法ListNode* partition(ListNode* head, int x) {ListNode *former = new Li...
题目链接：合并K个排序链表题意：合并k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。题解：这题的前身是合并两个排序链表。在剑指里有写。可以点击链接查看。。这个题，最好就是用小顶堆，O(nlog(K))。用c++的优先队列可以解决这个小顶堆。把每个节点丢进优先队列，然后以出队列的顺序作为新链表顺序代码： 1/**2 * Definition for singly-linked list.3 * struct ListNode {4 * int val;5 * ListNode *...
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。 示例 1：输入：[1,2,3,4,5]输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：输入：[1,2,3,4,5,6]输出：此...
原题给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例:输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5原题url：https://leetcode-cn.com/problems/partition-list/解题题目很好理解，重点在于区分大于等于和小于目标值的节点，判断其实是很简单的，主要在于如何拼接链表，以及最终如何返回。我发现，针对链表拼接...
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 示例 1：输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。示例 2：输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：输入：head = [1], pos = -1 输出：false 解...
代码实现：首先定义一个Node类：publicclass Node {protected Node next; //指针域 publicint data;//数据域 public Node( int data) { this. data = data; } //显示此节点 publicvoid display() { System. out.print( data + " "); } }接下来定义一个单链表，并实现相关方法：publicclass LinkList {//实现单链表publicstaticvoid main(String[] args) {LinkList linkList = new LinkList();linkList.addFirstNode(20);...
package com.chen.test;/*** @Description: 手写一个单向链表* @Author chenjianwen* @Date 2021/3/11**/ public class MySingleLinkedList<E> {private Node<E> first; //该链表的头节点private Node<E> last; //该链表的尾节点private int size; //该链表的大小/*** 从头部加入* @param e*/public void linkFirst(E e){Node<E> firstNode = first;Node<E> newNode = new Node<>();newNode.e = e;first = newNode;newNode.next = ...
单链表增加删除2.节点删除1.节点插入1.节点插入题目来源于PTA本题要求实现带头结点的单链表插入操作，插入成功返回1，否则返回0。函数接口定义：int insert_link ( LinkList L,int i,ElemType e);L是单链表的头指针，i为插入位置，e是插入的数据元素，插入成功返回1，否则返回0。裁判测试程序样例：#include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*Lin...
如题 (总结)首节点也存放了值,所以ListNode t = listNode; 直接从头开始遍历即可. 简单题目,但是构建的时候出了点问题,毕竟需要自己简单测测. 掌握链表的构建方法, 还要根据题目给的一段ListNode 代码来合理修改 . 注意, 面向题解答案编程后发现, 最后的链表末尾是不设置结点的!坑!https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-...