链表

单链表1.程序表 长处：物理空间间断，反对随机拜访 毛病：空间不够就须要扩容，破费工夫和空间；插入删除效率低下 2.单链表 长处：按需申请开释空间；插入删除常数工夫 毛病：不反对随机拜访 3.留神点 (1)在批改指针自身的内容时，也就是扭转指针自身存储的地址，咱们须要的是二级指针 void list_push_back(struct node** head, type x){ struct node* newnode = (struct node*)malloc(sizeof(struct node)); assert(newnode); newnode->data = x; newnode->next = NULL; //这里想扭转头结点的地址，让它指向一块新的空间，也就是扭转一个*类型的值->于是咱们须要**作为形式参数!! if (*head == NULL) { *head = newnode; } else { struct node* cur = *head; while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; }}4.实现 //forward_list<int> s;外面的插入删除：insert_after erase_aftervoid list_print(struct node* head){ struct node* cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n");}struct node* buy_newnode(type x){ struct node* newnode = (struct node*)malloc(sizeof(struct node)); assert(newnode); newnode->data = x; newnode->next = NULL; return newnode;}void list_push_back(struct node** phead, type x){ assert(phead); struct node*newnode = buy_newnode(x); //这里想扭转头结点的地址，让它指向一块新的空间，也就是扭转一个*类型的值->于是咱们须要**作为形式参数!! if (*phead == NULL) { *phead = newnode; } else { struct node* cur = *phead; while (cur->next != NULL) { cur = cur->next; } cur->next = newnode; }}//也须要传入二级指针：不论有没有元素，都须要扭转head的值，因为head必须是指向第一个结点的!!! void list_push_front(struct node** phead, type x){ assert(phead); struct node* newnode = buy_newnode(x); newnode->next = *phead; *phead = newnode; //验证高低都能够但下面的更加简洁 /*if (*phead == NULL) { *phead = newnode; } else { newnode->next = *phead; *phead = newnode; }*/}//一级指针不必查看：它可能就是一个空链表//二级指针须要查看：head是存在的，head有这个变量，那就肯定有个地址。phead外面寄存的就是head的地址void list_pop_front(struct node**phead){ assert(phead); assert(*phead);//这里头删,head肯定须要有值才能够删除 struct node* pre_head = *phead; *phead = (*phead)->next; free(pre_head);//开释它指向的空间}void list_pop_back(struct node**phead){ assert(phead); assert(*phead); struct node* t = *phead; if (t->next == NULL) { free(*phead); *phead = NULL; } else { while (t->next->next != NULL) { t = t->next; } t->next = NULL; free(t->next); } }struct node* list_find(struct node* head, type x){ assert(head); struct node* t = head; while (t != NULL) { if (t->data == x) { return t; } t = t->next; } return NULL;}void list_insert(struct node** phead, struct node* pos, type x){ assert(pos); assert(phead); if (pos == *phead) { list_push_front(phead, x); } else { struct node* t = *phead; while (t->next != pos) { t = t->next; } struct node*newnode = buy_newnode(x); newnode->next = pos; t->next = newnode; }}void list_erase(struct node**phead, struct node *pos){ assert(phead); assert(pos);//如果链表为空，pos不可能无效 if (pos == *phead) { list_pop_front(phead); } else { struct node* t = *phead; while (t->next != pos) { t = t->next; } t->next = pos->next; free(pos); //pos = NULL;//简直有效？因为pos是个形参，在这里置空无用，交给里面解决 }}void list_insert_after(struct node* pos, type x){ assert(pos); struct node * newnode = buy_newnode(x); newnode->next = pos->next; pos->next = newnode;}void list_erase_after(struct node* pos){ assert(pos->next); struct node* t = pos->next; pos->next = pos->next->next; free(t);}

1 链式前向星1.1 简介链式前向星可用于存储图，实质上是一个动态链表。 一般来说，存储图常见的两种形式为： 邻接矩阵邻接表邻接表的实现个别应用数组实现，而链式前向星就是应用链表实现的邻接表。 1.2 出处出处可参考此处。 2 原理链式前向星有两个外围数组： pre数组：存储的是边的前向链接关系last数组：存储的是某个点最初一次呈现的边的下标感觉云里雾里对吧，能够看看上面的具体解释。 2.1 pre数组pre数组存储的是一个链式的边的前向关系，下标以及取值如下： pre数组的下标：边的下标pre数组的值：前向边的下标，如果没有前向边，取值-1这里的前向边是指，如果某个点，作为起始点，曾经呈现过边x，那么，遍历到以该点作为起始点的下一条边y时，边y的前向边就是边x。 更新pre数组的时候，会遍历每一条边，更新该边对应的前向边。 比方，输出的有向边如下： n=6 // 顶点数[[0,1],[1,3],[3,5],[2,4],[2,3],[0,5],[0,3],[3,4]] // 边那么： 对于第一条边，下标为0，那么会更新pre[0]的值，边为0->1，而起始点点0还没有呈现过前向边，那么pre[0]=-1。这样就建设了边0->-1的一个链接关系，也就是说，对于起始点点0，它只有边0这一条边对于第二条边，下标为1，那么会更新pre[1]的值，边为1->3，而起始点点1还没有呈现过前向边，那么pre[1]=-1。这样就建设了边1->-1的一个链接关系，也就是说，对于起始点点1，它只有边1这一条边对于第三条边，下标为2，那么会更新pre[2]的值，边为3->5，而起始点点3还没有呈现过前向边，那么pre[2]=-1。这样就建设了边2->-1的一个链接关系，也就是说，对于起始点点3，它只有边2这一条边对于第四条边，下标为3，那么会更新pre[3]的值，边为2->4，而起始点点2还没有呈现过前向边，那么pre[3]=-1。这样就建设了边3->-1的一个链接关系，也就是说，对于起始点点2，它只有边3这一条边对于第五条边，下标为4，那么会更新pre[4]的值，边为2->3，而起始点点2，曾经呈现过一条边了，该边的下标是3，也就是前向边为3，那么就会更新pre[4]为前向边的值，也就是pre[4]=3。这样，就建设了边4->3->-1的一个链接关系，也就是对于起始点点2来说，目前有两条边，一条是边4，一条是边3对于第六条边，下标为5，那么会更新pre[5]的值，边为0->5，而起始点点0，曾经呈现过一条边了，该边的下标是边0，也就是前向边为0，那么就会更新pre[5]为前向边的值，也就是pre[5]=0。这样，就建设了边5->0->-1的一个链接关系，也就是对于起始点点0来说，目前有两条边，一条是边5，一条是边0对于第七条边，下标为6，那么会更新pre[6]的值，边为0->3，而起始点点0，曾经呈现过不止一条边了，最初一次呈现的边为边5，也就是前向边为5，那么就会更新pre[6]为前向边的值，也就是pre[6]=5。这样，就建设了边6->5->0->-1的一个链接关系，也就是对于起始点点0来说，曾经有三条边了，一条是边6，一条是边5，一条是边0对于第八条边，下标为7，那么会更新pre[7]的值，边为3->4，而起始点点3，曾经呈现过一条边了，该边的下标是边2，也就是前向边为2，那么就会更新pre[7]为前向边的值，也就是pre[7]=2。这样，就建设了边7->2->-1的一个链接关系，也就是对于起始点点3来说，目前有两条边，一条是边7，一条是边2这样，边的链接关系就建设下来了： 点 边的链接关系(边的下标)0 6->5->0->-11 1->-12 4->3->-13 7->2->-14 -15 -12.2 last数组last数组存储的是最初一次呈现的前向边的下标，下标以及取值如下： last数组的下标：点last数组的值：最初一次呈现的前向边的下标last数组会将所有值初始化为-1，示意所有的点在没有遍历前都是没有前向边的。 应用下面的数据举例： n=6 // 顶点数[[0,1],[1,3],[3,5],[2,4],[2,3],[0,5],[0,3],[3,4]] // 边last数组会与pre数组一起在遍历边的时候更新： 遍历到第一条边：下标为0，边为0->1，那么会更新以0为起始点的前向边的值，也就是本人，last[0]=0。而后，如果下一次遍历到了以0为起始点的边，比方0->5，那么0->5的前向边就是边0，而边0就存储在last[0]中，下次须要的时候间接取last[0]即可遍历到第二条边：下标为1，边为1->3，那么会更新以1为起始点的最初一次呈现的前向边的值，也就是last[1]=1遍历到第三条边：下标为2，边为3->5，那么会更新以3为起始点的最初一次呈现的前向边的值，也就是last[3]=2遍历到第四条边：下标为3，边为2->4，那么会更新以2为起始点的最初一次呈现的前向边的值，也就是last[2]=3遍历到第五条边：下标为4，边为2->3，那么会更新以2为起始点的最初一次呈现的前向边的值，也就是last[2]=4遍历到第六条边：下标为5，边为0->5，那么会更新以0为起始点的最初一次呈现的前向边的值，也就是last[0]=5遍历到第七条边：下标为6，边为0->3，那么会更新以0为起始点的最初一次呈现的前向边的值，也就是last[0]=6遍历到第八条边：下标为7，边为3->4，那么会更新以3为起始点的最初一次呈现的前向边的值，也就是last[3]=7在遍历每条边的时候，会先从last数组取值并赋给pre去生成链接关系，而后更新last数组中对应起始点的值为以后的边的下标。 3 代码3.1 生成数组生成last以及pre数组： public class Solution { private int[] pre; private int[] last; private void buildGraph(int n, int[][] edge) { int edgeCount = edge.length; pre = new int[edgeCount]; last = new int[n]; Arrays.fill(last, -1); for (int i = 0; i < edgeCount; i++) { int v0 = edge[i][0]; pre[i] = last[v0]; last[v0] = i; } }}pre的范畴与边数无关，而last的范畴与点数无关。一开始须要初始化last数组为-1，而后遍历每一条边： ...

（一）需要今儿还是链表中的一个算法——奇偶链表。 （二）奇偶链表1、问题形容给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点别离组合在一起，而后返回从新排序的列表。 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。 请留神，偶数组和奇数组外部的绝对程序应该与输出时保持一致。 你必须在 O(1) 的额定空间复杂度和 O(n) 的工夫复杂度下解决这个问题。 Demo1: 输出: head = [1,2,3,4,5]输入: [1,3,5,2,4]Demo2: 输出: head = [2,1,3,5,6,4,7]输入: [2,3,6,7,1,5,4]2、思路:定义一个新的额定空间一一遍历原链表将合乎奇偶数据的节点，放到对应申明的变量中 3、代码/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */function oddEvenList(head: ListNode | null): ListNode | null { if(head === null){ return head } let evenHead = head.next; // 定义偶数头结点 let odd = head // 定义奇数头结点 let even = evenHead // 定义偶数头结点 while(even != null && even.next!=null){//去除不成奇偶对 odd.next = even.next // 偶数的下一个，给了奇数初始头的下一个 odd = odd.next // 奇数节点右移一位 even.next = odd.next //奇数的下一个是偶数，给了新开队列的下一个 even = even.next // 偶数节点右移一位 } odd.next = evenHead // 奇数节点的开端的下一个，是偶数节拍板结点 return head};空间复杂度将是 O(1)工夫复杂度将是 O(n)以上 ...

（一）需要今儿持续是链表构造的算法——移除链表中的某个节点 （二）移除链表中的某个节点1、问题形容给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 Demo1: 输出：head = [1,2,6,3,4,5,6], val = 6输入：[1,2,3,4,5]Demo2: 输出：head = [], val = 1输入：[]Demo3: 输出：head = [7,7,7,7], val = 7输入：[]2、思路:定义一个头节点；迭代节点；判断值，如果值相等，那么把下一个节点的next赋值给以后节点的next值；3、代码/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} val * @return {ListNode} */var removeElements = function(head, val) { // 缺一个头节点，就定义一个 let prev = new ListNode(0) // 便于解决，首节点的值就雷同的状况 prev.next = head let curr = prev // 从新定义一个头节点 while(curr.next!=null){ const next = curr.next // 下一个节点 if (next.val == val){ // 下一个节点的值和目标值相等 curr.next = next.next // 把下一个节点的next赋值给以后节点的next值 }else{ curr = curr.next } } return prev.next};空间复杂度将是 O(1)工夫复杂度将是 O(n)以上 ...

（一）需要双指针解决链表的问题，还是蛮有意思~ 持续做~ （二）用双指针法删除链表倒数节点1、问题形容给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 输出：head = [1,2,3,4,5], n = 2输入：[1,2,3,5]2、思路:定义快慢指针，快指针挪动n个地位；fast 和 slow 同时挪动，fast挪动到最初一个节点时，slow的下一个节点就是要删除的节点3、题目/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} n * @return {ListNode} */var removeNthFromEnd = function(head, n) { let fast = head // 定义快指针 let slow = head // 定义慢指针 // 快指针挪动n个地位 while(n--){ fast = fast.next } // 如果fast为null 那么阐明删除的是第一个节点，返回第二个节点就OK if(!fast){ head = head.next return head } // fast 和 slow 同时挪动，fast挪动到最初一个节点时，slow的下一个节点就是要删除的节点 while(fast.next){ fast = fast.next slow = slow.next } slow.next = slow.next.next return head};空间复杂度将是 O(1)工夫复杂度将是 O(n)以上 ...

哨兵节点哨兵节点是为了简化解决链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第2个节点开始才真正保留有意义的信息。 用哨兵节点简化链表插入操作用哨兵节点简化链表删除操作应用哨兵节点能够简化创立或删除链表头节点操作的代码。 双指针删除倒数第k个节点题目：如果给定一个链表，请问如何删除链表中的倒数第k个节点？假如链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次。/** * @param {ListNode} head * @param {number} n * @return {ListNode} */var removeNthFromEnd = function(head, n) { const dummy = new ListNode(0, head); let front = head, back = dummy; for(let i = 0;i<n;i++) { front = front.next } while(front !== null) { front = front.next; back = back.next } back.next = back.next.next return dummy.next};链表中环的入口节点题目：如果一个链表中蕴含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。例如，在如图4.3所示的链表中，环的入口节点是节点3。反转链表反转链表题目：定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点var reverseList = function(head) { const prev = null; const cur = head; while(cur != null) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev}链表中的数组相加题目：给定两个示意非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和依然用单向链表示意？链表中的每个节点示意整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。剖析：要思考整数溢出的状况。 ...

合并两个有序链表LeetCode21. 合并两个有序链表 问题形容输出两个枯燥递增的链表，输入两个链表合成后的链表，咱们须要合成后的链表满足枯燥不减规定。 示例： 输出: {1,3,5},{2,4,6} 返回值: {1,2,3,4,5,6} 剖析问题既然给定的两个链表都是有序的，那么咱们能够判断两个链表的头结点的值的大小，将较小值的结点增加到后果中，而后将对应链表的结点指针后移一位，周而复始，直到有一个链表为空为止。 因为链表是有序的，所以循环终止时，那个非空的链表中的元素都比后面曾经合并的链表中的元素大，所以，咱们只须要简略地将非空链表接在合并链表的前面，并返回合并链表即可。 首先咱们须要先创立一个哨兵节点，而后将prehead指向链表l1和l2中比拟小的一个。如果相等的话，指向任意一个即可。而后将较小值对应的链表的指针后移一位。 咱们上面来看一下代码实现。 def mergeTwoLists(self, l1, l2): #合并后链表的哨兵结点 head=ListNode(-1,None) pre=head #循环遍历，将两个链表中的较小值插入到合并后的链表中 while l1 and l2: if l1.val <= l2.val: pre.next=l1 l1=l1.next else: pre.next=l2 l2=l2.next pre=pre.next #将残余的非空链表插入到合并链表的前面 if l1: pre.next=l1 else: pre.next=l2 return head.next其实，咱们这里也能够应用递归的形式来实现。 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def mergeTwoLists(self, l1, l2): #链表l1为空，不须要合并，间接返回l2 if(l1==None): return l2 #同理，l2为空，间接返回l1即可 if(l2==None): return l1 if(l1.val<=l2.val): l1.next=self.mergeTwoLists(l1.next,l2) return l1 else: l2.next=self.mergeTwoLists(l1,l2.next) return l2问题降级LeetCode23. 合并K个升序链表 ...

反转链表LeetCode206. 反转链表 问题形容给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。示例:输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]剖析问题首先，咱们依照题目的要求，先把图画进去，而后再剖析。 从图中咱们能够看到，反转前和反转后指针的指向产生了反转。所以，咱们在实现的过程中，咱们能够通过调整链表的指针来达到反转链表的目标。 咱们定义两个指针pre和cur。pre示意已反转局部的头结点，cur示意还没有反转局部的头结点。开始时cur=head，pre=None每次让cur->next=pre，实现一次部分反转。部分反转实现后，cur和pre同时向前挪动一位。循环上述过程，直到链表反转实现。 代码实现class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def reverse(self, head): cur = head #初始化时，pre为None pre = None while cur: next=cur.next cur.next = pre pre = cur cur = next return prehead=ListNode(1,None)cur=headfor i in range(2,6): tmp=ListNode(i,None) cur.next=tmp cur=cur.nexts=Solution()pre=s.reverse(head)while pre!=None: print(pre.val) pre=pre.next更多算法题解，关注公众号《程序员学长》，欢送退出。

链表全文概览 如果须要本文的PDF文档，请分割作者。或者关注公众【程序员学长】获取。 链表基础知识链表的分类链表是一种通过指针串联在一起的线性构造，次要分为单链表、双向链表和循环链表。 单链表单链表中每一个节点是由两局部组成，一个是数据域、一个是指针域（寄存指向下一个节点的指针），最初一个节点的指针域为空。 双向链表双向链表中的每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双向链表既能够向前查问也能够向后查问。 单向循环链表单向循环链表是指首尾相连的单链表。 双向循环链表双向循环链表是指首尾相连的双向链表。 链表的定义咱们在刷LeetCode的时候，因为链表的节点都默认定义好了，间接用就行了，然而在面试的时候，一旦要手写链表代码时，节点的定义是大家容易犯错的中央，所有咱们来看一下定义链表节点的形式。 #单链表class ListNode(object): def __init__(self, x): #数据域 self.val = x #指针域 self.next = None链表的操作单链表的删除操作删除链表中的q节点，只须要执行p->next=q->next，即让p的指针域指向q的下一个节点。 向单链表中减少一个节点在节点p后减少一个节点q，只须要执行q->next=p->next，p->next=q即可，这里肯定要留神执行的先后顺序。如果先执行p->next=q，那么原链表的p->next的信息就失落了。 解题有妙招引入哑结点哑结点也叫做哨兵节点，对于链表相干的题目，为了不便解决边界条件，个别咱们都会引入哑结点来不便求解。首先咱们来看一下什么是哑结点，哑结点是指数据域为空，指针域指向链表头节点的节点，它是为了简化边界条件而引入的。上面咱们来看一个具体的例子，例如要删除链表中的某个节点操作。常见的删除链表的操作是找到要删元素的前一个元素，如果咱们记为 pre。咱们通过：pre->next=pre->next->next来执行删除操作。如果此时要删除的是链表的第一个结点呢？就不能执行这个操作了，因为链表的第一个结点的前一个节点不存在，为空。如果此时你设置了哑结点，那么第一个结点的前一个节点就是这个哑结点。这样如果你要删除链表中的任何一个节点，都能够通过pre->next=pre->next->next的形式来进行，这就简化的代码的逻辑。 双指针法在求解链表相干的题目时，双指针也是十分罕用的思维，例如对于求解链表有环问题时，咱们申请两个指针，以一快一慢的速度在链表上行走，等他们相遇时，就能够晓得链表是否有环；或者在求链表的倒数k个节点时，申请两个指针，一个指针先走k步，而后两个指针再同时向后挪动，当先走的那个指针走到链表的开端时，另一个指针恰好指向了倒数第k个节点。 反转链表LeetCode206. 反转链表 问题形容给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。示例:输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]剖析问题首先，咱们依照题目的要求，先把图画进去，而后再剖析。 从图中咱们能够看到，反转前和反转后指针的指向产生了反转。所以，咱们在实现的过程中，咱们能够通过调整链表的指针来达到反转链表的目标。 咱们定义两个指针pre和cur。pre示意已反转局部的头结点，cur示意还没有反转局部的头结点。开始时cur=head，pre=None每次让cur->next=pre，实现一次部分反转。部分反转实现后，cur和pre同时向前挪动一位。循环上述过程，直到链表反转实现。 代码实现class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def reverse(self, head): cur = head #初始化时，pre为None pre = None while cur: next=cur.next cur.next = pre pre = cur cur = next return prehead=ListNode(1,None)cur=headfor i in range(2,6): tmp=ListNode(i,None) cur.next=tmp cur=cur.nexts=Solution()pre=s.reverse(head)while pre!=None: print(pre.val) pre=pre.next合并两个有序链表LeetCode21. 合并两个有序链表 ...

摘要：其实说实话，可能很多人仍然分不清线性表，程序表，和链表之间的区别和分割！本文分享自华为云社区《程序员必会本人设计线性表(程序表、链表)》，原文作者：bigsai。 前言其实说实话，可能很多人仍然分不清线性表，程序表，和链表之间的区别和分割！ 线性表：逻辑构造， 就是对外裸露数据之间的关系，不关怀底层如何实现，数据结构的逻辑构造大分类就是线性构造和非线性构造而程序表、链表都是一种线性表。程序表、链表：物理构造，他是实现一个构造理论物理地址上的构造。比方程序表就是用数组实现。而链表用指针实现次要工作。不同的构造在不同的场景有不同的区别。在Java中，大家都晓得List接口类型，这就是逻辑构造，因为他就是封装了一个线性关系的一系列办法和数据。而具体的实现其实就是跟物理构造相干的内容。比方程序表的内容存储应用数组的，而后一个get，set，add办法都要基于数组来实现,而链表是基于指针的。当咱们思考对象中的数据关系就要思考指针的属性。指针的指向和value。 上面用一个图来浅析线性表的关系。可能有些不太确切，然而其中能够参考，并且前面也会依据这个图举例。 线性表根本架构对于一个线性表来说。不论它的具体实现如何，然而它们的办法函数名和实现成果应该统一(即应用办法雷同、达成逻辑上成果雷同，差异的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分类似。最驰名的就是List的Arraylist和LinkedList，List是一种逻辑上的构造，示意这种构造为线性表，而ArrayList，LinkedList更多的是一种物理构造(数组和链表)。 所以基于面向对象的编程思维，咱们能够将线性表写成一个接口，而具体实现的程序表和链表的类能够实现这个线性表的办法，进步程序的可读性，还有一点比拟重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着常识的提高，咱们该当采纳泛型来实现更正当。至于接口的具体设计如下： package LinerList;public interface ListInterface<T> { void Init(int initsize);//初始化表 int length(); boolean isEmpty();//是否为空 int ElemIndex(T t);//找到编号 T getElem(int index) throws Exception;//依据index获取数据 void add(int index,T t) throws Exception;//依据index插入数据 void delete(int index) throws Exception; void add(T t) throws Exception;//尾部插入 void set(int index,T t) throws Exception; String toString();//转成String输入 }程序表程序表是基于数组实现的，所以所有实现须要基于数组个性。对于程序表的构造应该有一个存储数据的数组data和无效应用长度length. 还有须要留神的是初始化数组的大小，你能够固定大小，然而笔者为了可用性如果内存不够将扩充二倍。 上面着重解说一些初学者容易混同的概念和办法实现。这里把程序表比作一队坐在板凳上的人。 插入操作add(int index,T t)其中index为插入的编号地位，t为插入的数据，插入的流程为： (1)从后(最初一个有数据位)向前到index顺次后移一位，腾出index地位的空间 (2)将待插入数据赋值到index地位上，实现插入操作 能够看得出如果程序表很长，在靠前的中央如果插入效率比拟低(插入工夫复杂度为O(n))，如果频繁的插入那么复杂度挺高的。 删除操作同理，删除也是十分占用资源的。原理和插入相似，删除index地位的操作就是从index+1开始向后顺次将数据赋值到后面地位上，具体能够看这张图： 代码实现这里我实现一个程序表给大家作为参考学习： package LinerList;public class seqlist<T> implements ListInterface<T> { private Object[] date;//数组存放数据 private int lenth; public seqlist() {//初始大小默认为10 Init(10); } public void Init(int initsize) {//初始化 this.date=new Object[initsize]; lenth=0; } public int length() { return this.lenth; } public boolean isEmpty() {//是否为空 if(this.lenth==0) return true; return false; } /* * * @param t * 返回相等后果，为-1为false */ public int ElemIndex(T t) { // TODO Auto-generated method stub for(int i=0;i<date.length;i++) { if(date[i].equals(t)) { return i; } } return -1; } /* *取得第几个元素 */ public T getElem(int index) throws Exception { // TODO Auto-generated method stub if(index<0||index>lenth-1) throw new Exception("数值越界"); return (T) date[index]; } public void add(T t) throws Exception {//尾部插入 add(lenth,t); } /* *依据编号插入 */ public void add(int index, T t) throws Exception { if(index<0||index>lenth) throw new Exception("数值越界"); if (lenth==date.length)//扩容 { Object newdate[]= new Object[lenth*2]; for(int i=0;i<lenth;i++) { newdate[i]=date[i]; } date=newdate; } for(int i=lenth-1;i>=index;i--)//前面元素后挪动 { date[i+1]=date[i]; } date[index]=t;//插入元素 lenth++;//程序表长度+1 } public void delete(int index) throws Exception { if(index<0||index>lenth-1) throw new Exception("数值越界"); for(int i=index;i<lenth;i++)//index之后元素前挪动 { date[i]=date[i+1]; } lenth--;//长度-1 } @Override public void set(int index, T t) throws Exception { if(index<0||index>lenth-1) throw new Exception("数值越界"); date[index]=t; } public String toString() { String vaString=""; for(int i=0;i<lenth;i++) { vaString+=date[i].toString()+" "; } return vaString; }}链表学习c/c++的时候链表应该是很多人感觉很绕的货色，这个很大起因可能因为指针，Java尽管不间接应用指针然而咱们也要了解指针的原理和使用。链表不同于程序表(数组)它的构造像一条链一样链接成一个线性构造，而链表中每一个节点都存在不同的地址中，链表你能够了解为它存储了指向节点(区域)的地址，可能通过这个指针找到对应节点。 ...

单向链表以节点的形式来存储，蕴含data和next在内存中，链表的各个节点不肯定是间断存储的链表分有头节点的链表和没有头节点的链表，头节点用head示意代码次要是单向链表的增删改查import java.util.Stack;public class Demo2 { public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList(); //创立用户节点，并插入链表 UserNode user1 = new UserNode(1, "一一"); UserNode user3 = new UserNode(3, "三三"); UserNode user2 = new UserNode(2, "二二"); linkedList.addNode(user1); linkedList.addNode(user3); linkedList.addNode(user2); linkedList.getList(); System.out.println(); //按id大小插入 System.out.println("有序插入"); UserNode user5 = new UserNode(5, "五五"); UserNode user4 = new UserNode(4, "四四"); linkedList.addByOrder(user5); linkedList.addByOrder(user4); linkedList.getList(); System.out.println(); //按id批改用户信息 System.out.println("批改用户信息"); UserNode userEdit = new UserNode(1, "新一一"); linkedList.changeNode(userEdit); linkedList.getList(); System.out.println(); //依据id删除用户信息 System.out.println("删除用户信息"); linkedList.deleteNode(new UserNode(3, "")); linkedList.getList(); System.out.println(); //取得倒数第几个节点 System.out.println("取得倒数节点"); System.out.println(linkedList.getUserByRec(2)); System.out.println(); //翻转链表 System.out.println("翻转链表"); MyLinkedList newLinkedList = linkedList.reverseList(); newLinkedList.getList(); System.out.println(); //顺叙遍历链表 System.out.println("倒序遍历链表"); newLinkedList.reverseTraverse(); }}/** * 创立链表 */class MyLinkedList { private UserNode head = new UserNode(0, ""); /** * 在链表尾部增加节点 * * @param node 要增加的节点 */ public void addNode(UserNode node) { //创立一个辅助节点,用于遍历 UserNode temp = head; //找到最初一个节点 while (true) { //temp是尾节点就进行循环 if (temp.next == null) { break; } //不是尾结点就向后挪动 temp = temp.next; } temp.next = node; } /** * 遍历链表 */ public void getList() { System.out.println("开始遍历链表"); if (head.next == null) { System.out.println("链表为空"); } //创立辅助节点 UserNode temp = head.next; while (true) { //遍历实现就进行循环 if (temp == null) { break; } System.out.println(temp); temp = temp.next; } } /** * 按id程序插入节点 * * @param node */ public void addByOrder(UserNode node) { //如果一个节点都没用，直接插入 if (head.next == null) { head.next = node; return; } UserNode temp = head; while (temp.next != null && temp.next.id < node.id) { temp = temp.next; } //当指标node的id最大时，则不会执行if中的语句 if (temp.next != null) { node.next = temp.next; } temp.next = node; } /** * 依据id来批改节点信息 * * @param node 批改信息的节点 */ public void changeNode(UserNode node) { UserNode temp = head; //遍历链表，找到要批改的节点 while (temp.next != null && temp.id != node.id) { temp = temp.next; } //如果temp曾经是最初一个节点，判断id是否相等 if (temp.id != node.id) { System.out.println("未找到该用户的信息，请先创立该用户的信息"); return; } //批改用户信息 temp.name = node.name; } /** * 依据id删除节点,找到待删除节点的上一个节点 * * @param node 要删除的节点 */ public void deleteNode(UserNode node) { if (head.next == null) { System.out.println("链表为空"); return; } UserNode temp = head; //遍历链表，找到要删除的节点 while (temp.next != null && temp.next.id != node.id) { temp = temp.next; } //判断最初一个节点的是否要删除的节点 if (temp.next.id != node.id) { System.out.println("请先插入该用户信息"); return; } //删除该节点 temp.next = temp.next.next; } /** * 失去倒数的节点 * * @param index 倒数第几个数 * @return */ public UserNode getUserByRec(int index) { if (head.next == null) { System.out.println("链表为空!"); } UserNode temp = head.next; //记录链表长度 //所以length初始化为1 int length = 1; while (temp.next != null) { temp = temp.next; length++; } if (length < index) { throw new RuntimeException("链表越界"); } //假如有五个，倒数第一个相当于负数第五个 temp = head.next; for (int i = 0; i < length - index; i++) { temp = temp.next; } return temp; } /** * 翻转链表 * * @return 反转后的链表 */ public MyLinkedList reverseList() { //链表为空或者只有一个节点，无需翻转 if (head.next == null || head.next.next == null) { System.out.println("无需翻转"); } MyLinkedList newLinkedList = new MyLinkedList(); //用于保留正在遍历的节点 UserNode temp = head.next; //用于保留正在遍历节点的下一个节点 UserNode nextNode = temp.next; while (true) { //插入新链表 temp.next = newLinkedList.head.next; newLinkedList.head.next = temp; //挪动到下一个节点 temp = nextNode; nextNode = nextNode.next; if (temp.next == null) { //插入最初一个节点 temp.next = newLinkedList.head.next; newLinkedList.head.next = temp; head.next = null; return newLinkedList; } } } public void reverseTraverse() { if (head == null) { System.out.println("链表为空"); } UserNode temp = head.next; //创立栈，用于寄存遍历到的节点 Stack<UserNode> stack = new Stack<>(); while (temp != null) { stack.push(temp); temp = temp.next; } while (!stack.isEmpty()) { System.out.println(stack.pop()); } }}/** * 定义节点 */class UserNode { int id; String name; //用于保留下一个节点的地址 UserNode next; public UserNode(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "UserNode{" + "id=" + id + ", name='" + name + '\'' + '}'; }}

原创公众号：bigsai 文章珍藏在GitHub前言通过后面数据结构与算法前导我么晓得了数据结构的一些概念和重要性，那么咱们明天总结下线性表相干的内容。当然，我用本人的了解解分享给大家。 其实说实话，可能很多人仍然分不清线性表，程序表，和链表之间的区别和分割！ 线性表：逻辑构造， 就是对外裸露数据之间的关系，不关怀底层如何实现。程序表、链表：物理构造，他是实现一个构造理论物理地址上的构造。比方程序表就是用数组实现。而链表用指针实现次要工作。不同的构造在不同的场景有不同的区别。对于java来说，大家都晓得List接口类型，这就是逻辑构造，因为他就是封装了一个线性关系的一系列办法和数据。而具体的实现其实就是跟物理构造相干的内容。比方程序表的内容存储应用数组的，而后一个get，set，add办法都要基于数组来实现,而链表是基于指针的。当咱们思考对象中的数据关系就要思考指针的属性。指针的指向和value。 上面用一个图来浅析线性表的关系。可能有些不太确切，然而其中能够参考，并且前面也会依据这个图举例。 线性表根本架构对于一个线性表来说。不论它的具体实现办法如何，咱们应该有的函数名称和实现成果应该统一。你也能够感觉的到在一些构造的设计。比方List的Arraylist和LinkedList。Map的HashMap和currentHashMap他们的接口api都是雷同的，然而底层设计实现必定是有区别的。 所以，基于面向对象的编程思维，咱们能够将线性表写成一个接口，而具体实现的程序表和链表能够继承这个接口的办法，进步程序的可读性。 还有一点比拟重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着常识的提高，咱们该当采纳泛型来实现更正当。至于接口的具体设计如下： package LinerList;public interface ListInterface<T> { void Init(int initsize);//初始化表 int length(); boolean isEmpty();//是否为空 int ElemIndex(T t);//找到编号 T getElem(int index) throws Exception;//依据index获取数据 void add(int index,T t) throws Exception;//依据index插入数据 void delete(int index) throws Exception; void add(T t) throws Exception;//尾部插入 void set(int index,T t) throws Exception; String toString();//转成String输入 }程序表程序表是基于数组实现的，所以一些办法要基于数组的个性。对于程序表应该有的根底属性为一个数组data和一个length. 还有须要留神的是初始化数组的大小，你能够固定大小，然而笔者为了可用性如果内存不够将扩充二倍。当然这样很可能因为空间应用问题造成很大的节约。 一些根本的额办法就不说了，上面着重解说一些初学者容易混同的概念和办法实现。这里把程序表比作一队坐在板凳上的人。 插入add(int index,T t) 其中index为插入的编号地位，t为插入的数据-依据图片你就很好了解插入操作。当插入一个index时候，他的前面所有元素都要后移一位。你能够看的出插入时候整个操作的臃肿性。所以这也是程序表性能体现最差的中央,频繁的插入，删除。 删除同理，删除也是十分占用资源的。原理和插入相似，不过人走了，空一个小板凳前面的人须要往前挪。 其余操作其余操作就很简略了。比方如果依照编号获取数据getElem(int index)，你能够间接依据数据坐标返回。a[index]，而其余操作，能够通过遍历间接操作数组即可。 链表我想，表应该是很多人感觉很绕的货色，这个很大起因可能因为指针。很多人说java没指针，其实java他也有隐形指针。只不过不能间接用罢了。 指针建设的数据关系往往比数组这些要形象的多。对于指针域，你把他当成一个对象就好了，不过这个对象指向的是另一个同等级对象。对于这个关系，你能够比作每个person类。每个person类都有老公(老婆),而这个老公老婆也是一个理论对象，能够了解这更像一种逻辑约定关系，而不是硬生生的关系吧。 指针你能够思考成脑子记忆。下面的程序表咱们说它有序因为每个小板凳(数组)有编号，咱们能够依据这个来确定地位。而对于链表来说，你能够看作成一个站在操场上的一队人。而他的操作也略有不同，上面针对一些比拟非凡和重要的进行演绎。 ...

链表简介数组：对于索引有语义的状况，利用索引获取值，疾速查问。 随机拜访的能力链表：不适宜用于索引有语义的状况 真正的动静，不须要解决固定容量的问题构建构建节点类<?phpdeclare(strict_types=1);class Node{ // 该节点的元素值 public $e; // 下一个节点的指针 public $next; public function __construct($e = null, $next = null) { $this->e = $e; $this->next = $next; } // 将该节点对象的元素值用字符串输入 public function __toString(): string { return (string)$this->e; }} 构建链表实现类定义属性与构造函数<?phpdeclare(strict_types=1);require_once 'Node.php';class LinkedList{ // 链表头指针 private $head; // 链表中元素数量 private int $size; public function __construct() { $this->head = null; $this->size = 0; }} 获取链表无效元素数量// 获取链表无效元素数量public function getSize(): int{ return $this->size;} ...

先上代码#include <stdio.h>#include <stdlib.h>typedef struct nodeList { int data; //数据域 struct nodeList *next; //指针域} nodeList;//遍历链表void TraverseList(struct nodeList *head){ while(head != NULL){ printf("%d \n",head->data); head=head->next; }}//头插法nodeList *HeadCreatList(struct nodeList *head, int n){ struct nodeList *node; for (int i = 0; i < n; ++i) { node=(struct nodeList *)malloc(sizeof(struct nodeList)); node->data = i; node->next = head->next; head->next = node; } head->data = n; return head;}//尾插法nodeList *TailCreatList(struct nodeList *head, int n){ struct nodeList *node,*end; end = head; for (int i = 0; i < n; ++i) { node=(struct nodeList *)malloc(sizeof(struct nodeList)); node->data = i; end->next = node; end = node; } head->data = n; return head;}//删除某个值nodeList *deleteFromList(struct nodeList *head, int target){ struct nodeList *pre,*tmp; int count=0; tmp = head; pre = head; head= head->next; while(head != NULL){ if (head->data == target){ pre->next = head->next; count--; }else{ pre = head; count++; } head= head->next; } tmp->data = count; return tmp;}int main(){ struct nodeList *head,*node; head=(struct nodeList *)malloc(sizeof(struct nodeList)); //头结点 //head->data = NULL; head->next = NULL; //头插法 head = HeadCreatList(head, 5); printf("头插法: \n"); TraverseList(head); //尾插法 head = TailCreatList(head, 5); printf("尾插法: \n"); TraverseList(head); //删除 head = deleteFromList(head,2); printf("删除2: \n"); TraverseList(head); return 0;}执行后果： ...

原文链接：何晓东 博客 环路链表检测给定一个链表，如果它是有环链表，实现一个算法返回环路的结尾节点。有环链表的定义：在链表中某个节点的next元素指向在它后面呈现过的节点，则表明该链表存在环路。 起源：力扣（LeetCode）链接：https://leetcode-cn.com/probl... 解题思路 1遍历链表，同时将每次的后果放到 map 中，如果有元素反复呈现，则是有环形链表 代码/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func detectCycle(head *ListNode) *ListNode { visited := make(map[*ListNode]struct{}, 1) work := head for work != nil { _, ok := visited[work] if ok { return work } else { visited[work] = struct{}{} } work = work.Next } return nil}解题思路 2快慢指针求解：咱们定义两个指针，一快一满。慢指针每次只挪动一步，而快指针每次挪动两步。初始时，慢指针在地位 head，而快指针在地位 head.next。这样一来，如果在挪动的过程中，快指针反过来追上慢指针，就阐明该链表为环形链表。否则快指针将达到链表尾部，该链表不为环形链表。 ...

本文源码：GitHub·点这里 || GitEE·点这里 一、链表简介1、链表概念链表是一种物理存储单元上非间断、非程序的存储构造，数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列节点组成，节点能够在运行时动静生成，节点包含两个局部：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 2、根底特点内存存储 逻辑构造 特点形容 物理存储上是无序且不间断的；链表是由多个节点以链式构造组成；逻辑层面上看造成一个有序的链路构造；链表构造解决数组存储须要事后晓得元素个数的缺点，能够充分利用内存空间，实现灵便的内存动静治理。 二、单向链表1、根底形容 单向链表是链表的一种，其特点是链表的链接方向是单向的，链表的遍历要从头部开始程序读取；结点形成，head指针指向第一个成为表头结点，终止于最初一个指向NULL的指针。 2、根底操作增加数据 初始化head节点，作为链表的头；批改以后开端节点的next指针；新增加的节点房子在链表开端；删除数据 遍历找到要删除的节点，把删除节点前个节点的指针指向该删除节点的下个节点； 三、双向链表1、概念形容 双向链表也叫双链表，是链表的一种，链表的每个数据结点中都有两个指针，别离指向间接后继和间接前驱，从双向链表中的任意一个结点开始，都能够很疾速地拜访它的前驱结点和后继结点，链表构造的应用少数都是结构双向循环链表。 2、根底操作增加数据 遍历找到链表的最初一个节点；批改以后开端节点的next指针；新增加的节点房子在链表开端；增加最新尾节点的prev指针；删除数据 双向链表，基于要删除节点操作即可；操作上图中要删除的Node2节点；Node2.prev.next = Node2.next;Node2.next.prev = Node2.prev;通过上述流程的操作，就把链表中一个节点删除，剩下节点再度连接成链式构造。 3、源码剖析在Java的API中，LinkedList是典型的双向链表构造，上面基于LinkedList源码看双向链表的操作。 根底案例 public class M01_Linked { public static void main(String[] args) { List<User> userList = new LinkedList<>() ; User removeUser = new User(200,"Second") ; // 增加元素 userList.add(new User(100,"First")) ; userList.add(removeUser) ; userList.add(new User(300,"Third")) ; System.out.println("初始化："+userList); // 批改元素 userList.get(0).setUserName("Zero"); System.out.println("批改后："+userList); // 删除元素 userList.remove(removeUser) ; System.out.println("删除后："+userList); }}class User { private Integer userId ; private String userName ; public User(Integer userId, String userName) { this.userId = userId; this.userName = userName; } @Override public String toString() { return "User{" + "userId=" + userId + ", userName='" + userName + '\'' + '}'; } // 省略Get和Set办法}节点形容 ...

合并两个有序的链表1. 题目形容输出两个枯燥递增的链表，输入两个链表合成后的链表，当然咱们须要合成后的链表满足枯燥不减规定。 2. 示例无 3. 解题思路思路：非递归比拟两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前挪动一个结点。 步骤一后果会有一个链表先遍历完结，或者没有 第三个链表尾结点指向残余未遍历完结的链表 返回第三个链表首结点 递归办法： 4. Java实现非递归的实现办法：应用一个辅助的头部节点： ListNode root = new ListNode(-1)/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } ListNode node = new ListNode(-1); // 用于保留头部节点 ListNode root = node; while (list1 != null && list2 != null){ if (list1.val < list2.val){ node.next = list1; node = node.next; // 更新node节点，指向下一个 list1 = list1.next; }else{ node.next = list2; node = node.next; list2 = list2.next; } } // 可能某个链表还残余值,下列例子就链表2 会残余 // 比方链表1： 1->2->4 // 链表2： 3->5->6 if(list1 == null){ node.next = list2; } if (list2 == null){ node.next = list1; } return root.next; }}应用递归的实现办法：/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null){ return list2; } if (list2 == null){ return list1; } ListNode ret = null; if (list1.val < list2.val){ ret = list1; ret.next = Merge(list1.next, list2); }else{ ret = list2; ret.next = Merge(list1, list2.next); } return ret; }}5. Python实现比较简单的非递归的实现办法：#非递归实现合并两个有序的链表class Solution1: # 返回合并后列表 def Merge(self, pHead1, pHead2): if not pHead1: return pHead2 if not pHead2: return pHead1 start = None p = None while pHead1 and pHead2: if pHead1.val <= pHead2.val: print(pHead1.val) if start is None: start = p = pHead1 else: p.next = pHead1 p = p.next #更新p 结点 pHead1 = pHead1.next # 更新有序链表的结点 else: if start is None: start = p = pHead2 else: p.next = pHead2 p = p.next pHead2 = pHead2.next #可能某个链表始终还剩值 if not pHead1: #如果第一个链表都是空的话 p.next = pHead2 else: p.next = pHead1 return start 应用递归的实现办法：# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here if not pHead1: #如果一个链表不存在的话，返回另外一个链表 return pHead2 if not pHead2: return pHead1 if pHead1.val <= pHead2.val: ret = pHead1 ret.next = self.Merge(pHead1.next, pHead2) else: ret = pHead2 ret.next = self.Merge(pHead1, pHead2.next) return ret 如果您感觉本文有用，请点个“在看” ...

反转单链表1. 题目形容输出一个链表，反转链表后，输入新链表的表头。 2. 示例无 3. 解题思路输出的链表头指针为None或者整个链表只有一个结点时，反转后的链表呈现断裂，返回的翻转之后的头节点不是原始链表的尾结点。因而须要引入一个翻转后的头结点，以及一个指向以后结点的指针，一个指向以后结点前一个结点的指针，一个指向以后结点后一个结点的指针，防止出现断裂。 递归反转链表实现，绝对比拟容易一些 4. Java实现比较简单的非递归的实现办法：/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode ReverseList(ListNode head) { // 如果是head为空，或者只有一个节点，则间接返回 if (head == null || head.next == null){ return head; } ListNode p = head; ListNode newHead = null; // 新的头节点 while(p != null){ ListNode temp = p.next; // 保留p指向下一个节点的指针 p.next = newHead; newHead = p; // 更新头节点 p = temp; // 即 p = p.next ，更新p节点 } return newHead; }}应用递归的实现办法：/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode ReverseList(ListNode head) { // 应用递归的办法 if (head == null || head.next == null){ return head; } ListNode headNext = ReverseList(head.next); head.next.next = head; head.next = null; return headNext; }}5. Python实现比较简单的非递归的实现办法：#!/usr/bin/env python# -*- coding: utf-8 -*-"""__title__ = ''__author__ = 'mike_jun'__mtime__ = '2019-5-24'#目标： 反转单链表"""def reverseLink(head): #pass if not head or not head.next: return head p = head newHead = None while p: temp = p.next p.next = newHead newHead = p p = temp return newHead #创立一个单链表class Node(): def __init__(self, values): self.next = None self.values = values node1 = Node(1)node2 = Node(2)node3 = Node(3)node4 = Node(4)node1.next = node2node2.next = node3node3.next = node4 def printNode(head): result = [] while head: result.append(head.values) head = head.next print(result)printNode(node1)newNode = reverseLink(node1)printNode(newNode)应用递归的实现办法：/*pythonpublic class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode ReverseList(ListNode head) { // 应用递归的办法 if (head == null || head.next == null){ return head; } ListNode headNext = ReverseList(head.next); head.next.next = head; head.next = null; return headNext; }}如果您感觉本文有用，请点个“在看” ...

链表中倒数第k个结点1. 题目形容输出一个链表，输入该链表中倒数第k个结点。 2. 示例无 3. 解题思路应用双指针的办法： 如果在只心愿一次遍历的状况下, 寻找倒数第k个结点, 能够设置两个指针 第一个指针先往前走k-1步, 而后从第k步开始第二个指针指向头结点 而后两个指针一起遍历 当地一个指针指向尾节点的时候, 第二个指针正好指向倒数第k个结点 4. Java实现/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindKthToTail(ListNode head,int k) { // 快指针先走 k-1 步，慢指针指向头节点，两个节点一起走 // 当快指针走到尾，则慢指针找到 倒数 第 k 个节点 if (k <= 0 || head == null){ return null; } ListNode fastNode = head; ListNode slow = head; for (int i=0; i<k-1; i++){ if (fastNode.next == null){ // 判断是否会越界 return null; } fastNode = fastNode.next; } while(fastNode.next != null){ slow = slow.next; fastNode = fastNode.next; } return slow; }}5. Python实现# -*- coding:utf-8 -*-# class ListNode:# def __init__(self, x):# self.val = x# self.next = None class Solution: def FindKthToTail(self, head, k): # write code here if not head or k <= 0: return None pBehind = head for i in range(k-1): #找到第 k-1 个结点 if pBehind.next != None: pBehind = pBehind.next else: return None pHead = head while pBehind.next != None: # 而后一起往前走 pBehind = pBehind.next pHead = pHead.next return pHead 如果您感觉本文有用，请点个“在看” ...

链表是什么？上几篇文章中，分别介绍了动态数组，栈和队列，其中都是通过resize的方法进行动态扩容，从而实现了动态的数据结构，不过这种方法称为伪动态。真正的动态数据结构还要从链表说起，链表是真正的动态数据结构，一个动态数据结构不需要处理固定容量的问题，而且是最简单的动态数据结构，学好链表很重要，对后面复杂的数据结构是一种铺垫。链表见名知意，元素和元素之间就像链子一样拴住，元素也可以成为节点（Node），叫啥都行，反正能理解就好。每一个元素有两部分组成，一部分是元素本身，另一部分是下一个元素的引用。下文将元素本身就叫e，他的下一个引用就叫做next。 class Node<E>{ E e; //当前元素本身 Node next; //下一个元素的引用}上图表示，第一个元素的e是1，他的next是2。第二个元素的e是2，他的next是3。最后一个元素的e是3，但next为null，因为3就是最后一个元素，可以说如果一个元素的next为null，就代表他是最后一个元素。如果我想找到2，那就通过1去找，如果我想找到3，那不好意思，你也得通过1去找，因为1和3之间没有直接的关联，只能先通过1先找到2，2里面有存储3的地址。这也代表链表没有随机访问的能力，比如数组可以通过索引去找，效率很高。链表想找一个元素只能从头到尾遍历去找，查询效率低。 链表的实现首先创建了一个Node内部类，目的是只给LinkedList外部类用，外面的类是不可以操作Node对象的，这样做是比较安全的。成员变量分别是E e和Node next，e用于存储元素本身，next存储下一个元素的引用。LinkedList里面维护了两个变量，Node head和size，head用于存储目前链表的头元素，size用于维护链表里元素的个数。 public class LinkedList<E> { //内部维护一个Node对象，给外部类（LinkedList）使用 private class Node<E> { public E e; //当前Node对象的元素值 public Node next; //当前Node对象下一个对象的引用 public Node(E e,Node next) { this.e = e; this.next = next; } public Node(E e) { this.e = e; this.next = null; } public Node() { this.e = null; this.next = null; } } //头元素节点 private Node head; //当前链表节点个数 private int size; public LinkedList() { head = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; }}添加一个头节点添加头节点就是要创建一个新Node节点，新节点的e为666，新节点的next就指向了原来的头节点，改变指向后，要维护一下head，让新创建的这个节点变成头节点。最后维护一下size的个数。 ...

提出问题：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807 解题思路：设置两个指针指向两条链表，构造新节点存储两个当前指针节点的值，当前节点被遍历过后，指针后移。对于满10进1的情况，设置一个变量判断即可。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 flag = 0 new = ListNode(0) res = new while h1 or h2: temp = 0 if h1: temp += h1.val h1 = h1.next if h2: temp += h2.val h2 = h2.next if flag == 1: temp += 1 flag = 0 if temp >= 10: temp -= 10 flag = 1 res.next = ListNode(temp) res = res.next if flag == 1: res.next = ListNode(1) return new.next时间与空间复杂度： ...

提出问题：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 解决思路：合并链表很简单，设置两个指针遍历两个链表，同时遍历并比较大小，如果1链表的当前节点值较小，将该节点添加到新链表中，1链表遍历指针后移一位，直到两个链表内所有节点都添加到新链表中。注意：题目要求新链表是通过拼接给定的两个链表的所有节点组成的，所以初始新建一个头节点，将头节点下一个节点指针指向两个链表中的最小节点，最后返回头节点的下一个节点。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1==None: return l2 elif l2==None: return l1 else: h1 = l1 h2 = l2 head = ListNode(0) result = head while h1!=None and h2!=None: if h1.val <= h2.val: head.next = h1 h1 = h1.next else: head.next = h2 h2 = h2.next head = head.next if h1!=None: head.next = h1 if h2!=None: head.next = h2 return result.next时间与空间复杂度： ...

问题提出：反转一个单链表 解决思路：最先想到的是使用栈来存储链表的第一遍遍历的值。再重新遍历链表，遍历的同时弹出栈的元素（弹出的顺序刚好是链表节点值的倒序），为当前节点赋值当前弹出的值。python可以直接使用list结构存储遍历值，读取的时候倒序读取list元素，就相当于栈的原理。 代码如下(￣▽￣)： # Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def reverseList(self, head: ListNode) -> ListNode: l = [] temp = head while temp!=None: l.append(temp.val) temp = temp.next i = len(l)-1 temp2 = head while i>=0: temp2.val = l[i] i-=1 temp2 = temp2.next return head时间与空间消耗： 题目来源：https://leetcode-cn.com/probl...

本文介绍什么是链表，常见的链表有哪些，然后介绍链表这种数据结构会在哪些地方可以用到，以及 Redis 队列是底层的实现，通过一个小实例来演示 Redis 队列有哪些功能，最后通过 Go 实现一个双向链表。 目录1、链表 1.1 说明1.2 单向链表1.3 循环链表1.4 双向链表2、redis队列 2.1 说明2.2 应用场景2.3 演示3、Go双向链表 3.1 说明3.2 实现4、总结5、参考文献1、链表1.1 说明 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。 链表有很多种不同的类型：单向链表，双向链表以及循环链表。 优势:可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。链表允许插入和移除表上任意位置上的节点。 劣势:由于链表增加了节点指针，空间开销比较大。链表一般查找数据的时候需要从第一个节点开始每次访问下一个节点，直到访问到需要的位置，查找数据比较慢。 用途:常用于组织检索较少，而删除、添加、遍历较多的数据。 如：文件系统、LRU cache、Redis 列表、内存管理等。 1.2 单向链表链表中最简单的一种是单向链表， 一个单向链表的节点被分成两个部分。它包含两个域，一个信息域和一个指针域。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址，而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。 单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问哪个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。 1.3 循环链表循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。所不同的有以下几点： 1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是像单链表那样置为NULL。 2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域的值等于表头指针时，说明已到表尾。而非象单链表那样判断链域的值是否为NULL。 1.4 双向链表 双向链表其实是单链表的改进，当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。 在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域（当此“连接”为最后一个“连接”时，指向空值或者空列表）；一个存储直接前驱结点地址，一般称之为左链域（当此“连接”为第一个“连接”时，指向空值或者空列表）。 2、redis队列2.1 说明Redis 列表是简单的字符串列表，按照插入顺序排序。你可以添加一个元素到列表的头部（左边）或者尾部（右边） Redis 列表使用两种数据结构作为底层实现：双端列表(linkedlist)、压缩列表(ziplist) 通过配置文件中(list-max-ziplist-entries、list-max-ziplist-value)来选择是哪种实现方式 在数据量比较少的时候，使用双端链表和压缩列表性能差异不大，但是使用压缩列表更能节约内存空间 redis 链表的实现源码 redis src/adlist.h 2.2 应用场景消息队列，秒杀项目 秒杀项目: 提前将需要的商品码信息存入 Redis 队列，在抢购的时候每个用户都从 Redis 队列中取商品码，由于 Redis 是单线程的，同时只能有一个商品码被取出，取到商品码的用户为购买成功，而且 Redis 性能比较高，能抗住较大的用户压力。 ...

以下是本人完成的一个C语言建立链表并进行增删查改操作的程序，为方便学习，本人将整个程序分为头文件和主函数两部分： 1.头文件(函数部分)(1)初始化函数 #include <stdio.h>#include <stdlib.h>typedef struct { int *head; int length; int capacity;} Toslist; //Toslist类型//初始化顺序表Toslist initSeqlist() { Toslist list; list.length = 0; list.capacity = 5; list.head = (int *)malloc(10 * sizeof(int)); if (!list.head) { printf("初始化失败！\n"); exit(0); } return list;}（2）打印函数 //打印顺序表void displayList(Toslist list) { for (int i = 0; i < list.length; i++) { printf("%d ", list.head[i]); } printf("\n");}(3)插入函数 //插入元素Toslist add(Toslist list, int elem, int pos) { if (list.length == list.capacity) { int *temp = (int *)realloc(list.head, (list.capacity + 1) * sizeof(int));//判断空间是否足够，不够就另建链表//不直接用head而引入temp的作用：防止空间分配失败导致head失去原来的链表 if (!temp) { list.head = temp; list.capacity += 1; } } //插入位置及以后的元素后移 for (int i = list.length - 1; i >= pos; i--) { list.head[i + 1] = list.head[i]; } list.head[pos] = elem; list.length ++; return list; if (pos > list.length || pos < 0) printf("插入位置错误！\n"); return list;}（4）删除函数 ...

无可奈何花落去 似曾相识燕归来 前言两个链表list1和list2如果中间有一个交汇点。怎样在线性时间内求出这个交汇点？ 思路分别求出两个链表的长度 把长链做偏移和短链一样长 同时移动两个链表的首指针，判断节点是否相等 相等则找到交叉点 代码实现 // 定义节点 typedef struct Node { int data; struct Node *next; } Node; /// 计算链表的长度 int getListLength(Node *list) { int length = 1; while (list->next != NULL) { length++; list = list->next; } return length; } // 长链表做偏移 Node* relocateNode (Node *list, int offset) { Node *node1 = list; for (NSInteger i = 0; i < offset; i++) { node1 = node1->next; } return node1; } int findCommonNode (Node *list1, Node *list2) { // 计算两个链表的长度 int list1Length = getListLength(list1); int list2Length = getListLength(list2); // 计算两个链表的长度差值 int offset = abs(list1Length-list2Length); // 记录长链短链 Node *longList = list1; Node *shortList = list2; if (list1Length < list2Length) { longList = list2; shortList = list1; } // 长链做偏移 ，偏移后和短链一样长 longList = relocateNode(longList, offset); // 同时移动两个链表的首指针 while (shortList != NULL) { if (longList->data == shortList->data) { // 如果节点值相等 找到交叉点 return longList->data; } longList = longList->next; shortList = shortList->next; } return 0; } int main(int argc, const char * argv[]) { @autoreleasepool { Node *node1 = malloc(sizeof(Node)); node1->data = 1; Node *node2 = malloc(sizeof(Node)); node2->data = 2; Node *node3 = malloc(sizeof(Node)); node3->data = 3; Node *node4 = malloc(sizeof(Node)); node4->data = 4; Node *node5 = malloc(sizeof(Node)); node5->data = 5; Node *node6 = malloc(sizeof(Node)); node6->data = 6; Node *node7 = malloc(sizeof(Node)); node7->data = 7; node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node5; node5->next = node6; node6->next = NULL; node7->next = node4; Node *list1 = node1; // 1 2 3 4 5 6 Node *list2 = node7; // 7 4 5 6 int commonValue = findCommonNode(list1, list2); NSLog(@"commonValue: %d\b", commonValue);// 4 } return 0; }测试结果 ...

线性表定义及实现线性表是最常用的数据结构，抽象上讲表是存储具有先后顺序元素数据的结构，实现上分为顺序表和链式表。顺序表一般采用C语言中数组实现，数组中存储数据，依靠数据索引确定先后顺序信息，物理上存储连续。根据C中数组的定义，移动，动态申请空间，复制等操作，可以想象顺序表在处理动态变化线性表上的缺点。链式表一般采用C语言中结构体struct实现，每个结构体节点除了存储数据，还存储元素先后顺序信息，物理上存储不连续；根据是否存储前置元素可分为单链表双链表等。插入，删除，移动等动态操作较为方便。 编程实例问题及解决思路projecteuler的Problem10求2000000以内所有素数的和，首先要找到2000000所有素数。判断一个是是否素数，如果采用比之小的数去除，则除法运行次数太多。所以建立一个素数链表，用该链表里的素数去除，判断是否素数；一旦是素数，插入或追加到该链表中，为判断后续数字做嫁衣。详细介绍：https://segmentfault.com/a/11... 代码实现结构定义struct intNode;typedef struct intNode sIntNode;typedef sIntNode *pIntNode;struct intNode{ long long int data; pIntNode next; pIntNode prv;};操作方法//初始化pIntNode elrInitListInt(long long int data){ pIntNode tmp = NULL; tmp = (pIntNode)malloc(sizeof(sIntNode)); tmp->data = data; tmp->prv = tmp->next = tmp; return tmp;}//释放void elrPushListInt(pIntNode pList, long long int data){ pIntNode tmp = NULL; tmp = (pIntNode)malloc(sizeof(sIntNode)); tmp->data = data; tmp->next = pList; tmp->prv = pList->prv; pList->prv->next = tmp; pList->prv = tmp;}//追加元素void elrFreeListInt(pIntNode pList){ pIntNode tmp; while (pList->prv != pList){ tmp = pList->prv; pList->prv = tmp->prv; tmp->prv->next = pList; free(tmp); } free(pList); pList = NULL;}素数全局变量初始化方法pIntNode globalPrime;int globalPrimeCount;long long int globalPrimeNum;void initGlobalPrime(){ globalPrime = elrInitListInt(2); elrPushListInt(globalPrime, 3); elrPushListInt(globalPrime, 5); globalPrimeNum = 0; globalPrimeCount = 3;}void freeGlobalPrime(){ elrFreeListInt(globalPrime); globalPrimeNum = 0; globalPrimeCount = 0; }判断是否素数//优化：//1.用链表的素数去除，减少除法运行次数,本质上应该就是Eratosthenes埃拉托斯特尼筛选法//2.采用6n+1,6n+5才可能是素数，减少运行次数 ...

什么是链表？链表是一种数据结构，由许多称为“节点”的迷你数据结构组成。节点链接在一起形成一个列表。 整个链表，由3个节点链接在一起组成。 每个节点包含2个属性它的价值。这可以是任何东西：整数，字符，字符串，对象等。指向序列中下一个节点的指针。一些定义头节点：头节点只是链表中的第一个节点。从上面的例子可以看出，包含'5'的节点是第一个节点，因此是头部。 '尾节点：尾节点是序列中的最后一个节点。由于它是最后一个节点，因此它指向null，因为序列中没有下一个节点。在上面的示例中，包含“3”的节点将是尾节点。 单身联系与双重联系在链接列表方面，有两种主要类型。 那些“单独”联系的，以及那些“双重”联系的。 单独链接意味着每个节点仅指向最多1个其他节点，即其前面的节点。这在上面的例子中展示。 双重链接意味着每个节点可以指向其他2个节点，前面的节点和它后面的节点。正如我们从下面的例子中可以看到的那样，由于头节点之前没有节点（即5），因此其中一个指针指向null。 代码是如何工作的呢？编码链接列表可能是4行问题或400行问题。这取决于你想要如何接近它。 在最简单的层面上，就像我们讨论的那样，链表只是一堆连接的节点。 因此，我们真正需要创建此结构的只是一个节点对象。 class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNode在这里我们可以看到我们只是创建了一个具有value和nextNode属性的类。 要创建节点，我们只需传入一个值。 node1 = linkedListNode("3") # "3"node2 = linkedListNode("7") # "7"node3 = linkedListNode("10") # "10"在这里，我们创建了3个单独的节点。 下一步就是将它们连接在一起。 node1.nextNode = node2 node2.nextNode = node3 上面的第一行使node1指向node2： “3”→“7” 上面的第二行使node2指向node3： “7”→” 10" 总之，我们留下了一个链接列表，如下所示： “3”→” 7" →” 10" →null 注意：“10”指向null，因为没有为node3分配nextNode，并且默认的nextNode为Null。 就像我之前提到的，有很多不同的方法可以做到这一点。这只是最简单的。 遍历链接列表如果您正在进行编程访谈，并且您会收到链接列表问题，那么您将无法获得所有节点。 所有你得到的是头节点。 从该头节点，您必须获得列表的其余部分。 首先让我们了解如何从Python中的节点获取值和nextNode。 假设我们有一个名为'node'的节点。 ...

概要之前我们分别学习了解了动态数组、栈、队列，其实他们的底层都是依托静态数组来实现的、只是通过我们定义的resize方法来动态扩容解决固定容量的问题，那么我们即将学习的链表，它其实是一种真正的动态数据结构。介绍链表是一种最简单的动态数据结构，它能够辅助组成其它的数据结构，链表中的元素可存储在内存中的任何地方（不需要连续的内存，这一点和我们的数组具有很大的区别，数组需要连续的内存），链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串接在一起。存储链表的数据的我们一般称为节点（Node），节点一般分为两部分，一部分存储我们真正的数据，而另外一部分存储的是下一个节点的引用地址。class Node{ private E e; // 存储的真正元素 private Node next; // 存储下一个node的引用地址(指向下一个node)}比如现在我们将元素A、B、C三个节点添加到链表中，示意图如下：从图中节点A到节点B之间的箭头代表，节点A指向了节点B（NodeA.next = NodeB），因为在实际业务中我们的链表长度不可能是无穷无尽的，基本上都是有限个节点，通常定义链表中的最后一个元素它的next存储的是NULL（空），换句话说，如果在链表中，一个节点的next是空（NULL）的话，那么它一定是最后一个节点（对应我们图中的C节点）。根据我们上面介绍的链表基本结构，下面我们用代码定义一下链表的基本骨架（这里我们引入了一个虚拟的头结点，下面我们会作说明）public class LinkedList<E> { /** * 虚拟的头结点 / private Node dummyHead; /* * 链表中节点的个数 / private int size; public LinkedList() { // 创建一个虚拟的头结点 dummyHead = new Node(); } // 节点定义 private class Node { // 存储节点的元素 public E e; // 存储下一个节点的地址 public Node next; public Node() { } public Node(E e) { this.e = e; } public Node(E e, Node next) { this.e = e; this.next = next; } @Override public String toString() { return “Node{” + “e=” + e + “, next=” + next + ‘}’; } }}后面我们对链表的添加节点、删除节点以及查询节点，代码实现都会基于这个基本骨架向链表中添加节点思路分析：一般我们向链表中添加节点，基本思路：找到添加节点位置的前一个节点preNode，然后再改变链表的地址引用；由于链表的第一个节点也就是头结点没有前节点，此时我们为了操作方便，为链表新增了不存储任何元素的一个虚拟的头结点dummyHead（不是必须的，对用户来讲是不可见的），其实链表中真正的第一个节点是节点A（dummyHead.next），这样我们就能保证了，链表中存储元素的节点都有前一个节点。下面我们来看一下，如果现在有一个节点D，我们准备把它插入到节点B的位置，我们需要做哪些操作第一步：我们首先要找到节点B的前一个节点，也就是节点A第二步：将新节点D的指向指到节点B（NodeD.next = NodeA.next），然后再将节点A的指向，指到节点D（NodeA.next = NodeD），这样我们的节点就能串接起来了代码实现：/* * 向链表中指定位置插入节点（学习使用，真正插入不会指定索引） * * @param index 索引的位置 * @param e 节点元素 /public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException(“不是有效的索引”); } Node prev = dummyHead; // 找到index位置的前一个节点 for (int i = 0; i < index; i++) { prev = prev.next; } // 新建一个节点，进行挂接 Node node = new Node(e); node.next = prev.next; prev.next = node; size++;}链表的遍历进行链表遍历，我们需要从链表中真正的第一个元素开始，也就是dummyHead.next/* * 获取链表中index位置的元素 * * @param index 索引的位置 * @return 节点的元素 /public E get(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException(“不是有效的索引”); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e;}修改链表中元素/* * 修改链表中index位置节点的元素 * * @param index 索引的位置 * @param e 节点的元素 /public void set(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException(“不是有效的索引”); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } cur.e = e;}查找链表中是否包含某元素/* * 查找链表中是否包含元素e * * @param e * @return /public boolean contains(E e) { Node cur = dummyHead.next; while (cur != null) { if (cur.e.equals(e)) { return true; } cur = cur.next; } return false;}删除链表中的元素在链表中删除元素，与在链表中添加元素有点类似第一步：我们首先找到删除节点位置的前一个节点，我们用prev表示，被删除的节点我们用delNode表示第二步：改变链表的引用地址：prev.next = delNode.next（等同于，将节点在链表中删除）/* * 删除链表中index位置的节点 * * @param index */public void remove(int index) { if (index < 0 || index > size) { throw new IllegalArgumentException(“不是有效的索引”); } Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size–;}完整版代码GitHub仓库地址：Java版数据结构-链表 欢迎大家【关注】和 【Star】至此笔者已经为大家带来了数据结构：静态数组、动态数组、栈、数组队列、循环队列、链表；接下来，笔者还会一一的实现其它常见的数组结构，大家一起加油!静态数组动态数组栈数组队列循环队列链表循环链表二分搜索树优先队列堆线段树字典树AVL红黑树哈希表….持续更新中，欢迎大家关注公众号 小白程序之路（whiteontheroad），第一时间获取最新信息！！！笔者博客地址：http:www.gulj.cn ...

通过对《Redis设计与实现》一书的学习，我打算动手自己实现一份“Redis源代码”作为自己的学习记录。对Redis感兴趣的同学可以查看我的另一篇文章 造个轮子 | 自己动手写一个Redis。本章介绍的是Redis源代码中的双端链表list的实现。双端链表list的实现list的API（1）创建一个不包含任何结点的新链表list *listCreate(void);（2）释放给定链表，以及链表中的所有结点void listRelease(list *l);（3）将一个包含给定值的新节点添加到给定链表的表头list listAddNodeHead(list l, void *value);（4）将一个包含给定值的新节点添加到给定链表的表尾list listAddNodeTail(list l, void *value);（5）将一个包含给定值的新节点添加到给定结点的之前或之后list listInsertNode(list l, listNode old_node, void value, int after);（6）从链表中删除给定结点list listDelNode(list l, listNode *node);（7）复制一个给定链表的副本list listDup(list orig);（8）查找并返回链表中包含给定值的结点listNode listSearchKey(list l, void *key);（9）返回链表在给定索引上的结点listNode listIndex(list l, long index);（10）将链表结点的表位结点弹出，然后将被弹出的结点插入到链表的表头，成为新的表头结点void listRotate(list *l);头文件#ifndef ADLIST_H#define ADLIST_H//双端链表//双端链表的结点typedef struct listNode{ struct listNode *prev;//指向点一个结点的指针 struct listNode *next;//指向下一个结点的指针 void *value;//结点存放的值}listNode;//链表typedef struct list{ listNode *head;//头结点 listNode *tail;//尾结点 int len;//链表的长度 //用于实现多态链表所需的类型的特定函数 //函数指针 //用于复制链表结点所保存的值 void *(*dup)(void *ptr); //用于释放链表结点所保存的值 void (*free)(void *ptr); //用于对比 int (*match)(void *ptr, void *key);}list;//定义对链表进行操作的宏//获取链表长度#define listLength(l) ((l)->len)//获取链表的头结点#define listFirst(l) ((l)->head)//获取链表的尾结点#define listLast(l) ((l)->tail)//获取前一个结点#define listPrevNode(n) ((n)->prev)//获取下一个结点#define listNextNode(n) ((n)->next)//获取该结点的值#define listNodeValue(n) ((n)->value)//设置复制操作的函数指针#define listSetDupMethod(l,m) ((l)->dup = (m))//设置释放操作的函数指针#define listSetFreeMethod(l,m) ((l)->free = (m))//设置对比操作的函数指针#define listSetMatchMethod(l,m) ((l)->match = (m))//获取复制链表结点的函数指针#define listGetDupMethod(l) ((l)->dup)//获取释放链表结点的函数指针#define listGetFree(l) ((l)->free)//获取比较链表结点的函数指针#define listGetMatchMethod(l) ((l)->match)//创建一个不包含任何结点的新链表list *listCreate(void);//释放给定链表，以及链表中的所有结点void listRelease(list *l);//将一个包含给定值的新节点添加到给定链表的表头list *listAddNodeHead(list *l, void *value);//将一个包含给定值的新节点添加到给定链表的表尾list *listAddNodeTail(list *l, void *value);//将一个包含给定值的新节点添加到给定结点的之前或之后list *listInsertNode(list *l, listNode *old_node, void *value, int after);//从链表中删除给定结点list *listDelNode(list *l, listNode *node);//复制一个给定链表的副本list *listDup(list *orig);//查找并返回链表中包含给定值的结点listNode *listSearchKey(list *l, void *key);//返回链表在给定索引上的结点listNode listIndex(list l, long index);//将链表结点的表位结点弹出，然后将被弹出的结点插//入到链表的表头，成为新的表头结点void listRotate(list l);#endiflist API的实现#include <stdio.h>#include <stdlib.h>#include <string.h>#include “adlist.h”//创建一个不包含任何结点的新链表list listCreate(void){ list l=(list)malloc(sizeof(list)); //没有结点 l->head=NULL; l->tail=NULL; l->len=0; l->dup=NULL; l->free=NULL; l->match=NULL; return l;}//释放给定链表，以及链表中的所有结点void listRelease(list l){ if(l==NULL){ return ; } //没有head(没有结点) if(l->head==NULL){ return ; } //保证了链表是有结点存在的 //用来移动的指针，指向第一个结点 listNodetemp=l->head; while(temp->next!=NULL){ temp=temp->next; //使用链表对应释放value的free来释放value的值 if(l->free!=NULL){ l->free(temp->value); }else{ printf(“PIG Redis WARNING : List->free is not define.\n”); } free(temp->prev); } free(temp); l->head=NULL; l->tail=NULL; free(l); l=NULL; return;}//将一个包含给定值的新节点添加到给定链表的表头list listAddNodeHead(list l, void value){ if(l==NULL){ printf(“PIG Redis ERROR : List NULL.\n”); return NULL; } //链表中没有结点 if(l->head==NULL){ l->head=(listNode)malloc(sizeof(listNode)); l->head->next=NULL; l->head->prev=NULL; //使用链表对应复制value的dup来复制value的值 if(l->dup!=NULL){ l->head->value=l->dup(value); }else{ printf(“PIG Redis WARNING : List->dup is not define.\n”); l->head->value=value; }/ int c=(int)(l->head->value); printf("%d====\n",c);/ l->len=1; //头尾指针都指向新的结点 l->tail=l->head; return l; }else{ listNodenewone=(listNode)malloc(sizeof(listNode)); //newone->value=value; //使用链表对应复制value的dup来复制value的值 if(l->dup!=NULL){ newone->value=l->dup(value); }else{ printf(“PIG Redis WARNING : List->dup is not define.\n”); newone->value=value; }/ int cc=(int)(newone->value); printf("%d====\n",cc);/ newone->next=l->head; l->head->prev=newone; //新节点设为头结点 l->head=newone; newone->prev=NULL; l->len++; return l; }}//将一个包含给定值的新节点添加到给定链表的表尾list listAddNodeTail(list l, void value){ if(l==NULL){ printf(“PIG Redis ERROR : List NULL.\n”); return NULL; } //链表中没有结点 if(l->head==NULL){ l->head=(listNode)malloc(sizeof(listNode)); //l->head->value=value; //使用链表对应复制value的dup来复制value的值 if(l->dup!=NULL){ l->head->value=l->dup(value); }else{ printf(“PIG Redis WARNING : List->dup is not define.\n”); l->head->value=value; } l->head->next=NULL; l->head->prev=NULL; l->tail=l->head; l->len=1; return l; }else{ listNodetemp=(listNode)malloc(sizeof(listNode)); //temp->value=value; //使用链表对应复制value的dup来复制value的值 if(l->dup!=NULL){ temp->value=l->dup(value); }else{ printf(“PIG Redis WARNING : List->dup is not define.\n”); temp->value=value; } temp->next=NULL; temp->prev=l->tail; l->tail->next=temp; l->tail=temp; l->len++; return l; }}//将一个包含给定值的新节点添加到给定结点的之前或之后//after为1表示之后，after为0表示之前list *listInsertNode(list *l, listNode *old_node, void *value, int after){ listNode newone=(listNode)malloc(sizeof(listNode)); //newone->value=value; //使用链表对应复制value的dup来复制value的值 if(l->dup!=NULL){ newone->value=l->dup(value); }else{ printf(“PIG Redis WARNING : List->dup is not define.\n”); newone->value=value; } l->len++; if(after){ newone->next=old_node->next; newone->prev=old_node; old_node->next->prev=newone; old_node->next=newone; //检查原来的temp是否为tail if(l->tail==old_node){ l->tail=newone; } return l; }else{ newone->next=old_node; newone->prev=old_node->prev; old_node->prev->next=newone; old_node->prev=newone; //检查原来的temp是否为头结点 if(l->head==old_node){ l->head=newone; } return l; }} //从链表中删除给定结点list *listDelNode(list *l, listNode node){ l->len–; //使用链表对应释放value的free来释放value的值 if(l->free!=NULL){ l->free(node->value); }else{ printf(“PIG Redis WARNING : List->free is not define.\n”); } //要删除的是最后一个结点 if(l->head==node&&l->tail==node){ free(node); l->head=NULL; l->tail=NULL; return l; }else if(l->head==node){ printf(“head\n”); l->head=node->next; l->head->prev=NULL; free(node); return l; }else if(l->tail==node){ l->tail=node->prev; l->tail->next=NULL; free(node); return l; } node->prev->next=node->next; node->next->prev=node->prev; free(node); return l;}//复制一个给定链表的副本list listDup(list orig){ if(orig==NULL){ return NULL; } //该链表没有结点 if(orig->head==NULL){ listl=listCreate(); return l; }else{ listl=listCreate(); listNodetemp=orig->head; while(temp!=NULL){ //向表尾插入 l=listAddNodeTail(l,temp->value); temp=temp->next; } return l; }}//查找并返回链表中包含给定值的结点listNode *listSearchKey(list *l, void key){ if(l==NULL){ printf(“PIG Redis ERROR : List NULL.\n”); return NULL; //链表中没有结点 }else if(l->head==NULL){ printf(“PIG Redis ERROR : List does’t have nodes.\n”); return NULL; }else{ listNodetemp=l->head; //检查是否定义了比较value的函数 if(l->match==NULL){ printf(“PIG Redis ERROR : List->match is not define.\n”); return NULL; } //match函数当两者相等时返回1 while(temp!=NULL&&!(l->match(key,temp->value))){ temp=temp->next; } if(temp==NULL){ printf(“PIG Redis ERROR : List doesn’t have this node.\n”); return NULL; }else{ return temp; } }} //返回链表在给定索引上的结点,index从0开始listNode *listIndex(list l, long index){ if(l==NULL){ printf(“PIG Redis ERROR : List NULL.\n”); return NULL; }else if(l->head==NULL){ printf(“PIG Redis ERROR : List doesn’t have node.\n”); return NULL; } listNodetemp=l->head; for(int i=0;i<index&&temp!=NULL;i++){ temp=temp->next; } if(temp==NULL){ printf(“PIG Redis ERROR : Subscript out of range.\n”); return NULL; } return temp;}//将链表结点的表尾结点弹出，然后将被弹出的结点插//入到链表的表头，成为新的表头结点void listRotate(list l){ if(l==NULL){ printf(“PIG Redis ERROR : List NULL.\n”); return ; }else if(l->head==NULL){ printf(“PIG Redis ERROR : List doesn’t have node.\n”); return ; }else if(l->head==l->tail){ printf(“PIG Redis ERROR : List only have one node.\n”); return ; } listNodenode=l->tail->prev; l->tail->prev->next=NULL; l->tail->next=l->head; l->head->prev=l->tail; l->head=l->tail; l->tail=node; l->head->prev=NULL;}int intMatch(void *ptr, void *key){ int *a=(int *)ptr; int *b=(int *)key; return (*a==*b)?1:0;}void *intDup(void ptr){ return ptr;}int main(){ printf(“listCreate()\n”); listl=listCreate(); printf("%d\n",l->len); listSetDupMethod(l,&intDup); int b=111; int a=&b; l=listAddNodeHead(l,a); printf("%d\n",l->len); //使用void指针的时候需要强制转换 int *c=(int *)(l->head->value); printf("%d\n",*c); int bb=12; int aa=&bb; l=listAddNodeHead(l,aa); //listInsertNode(l,l->head,a,1); //l=listAddNodeTail(l,aa); //printf("%d\n",l->len); //l=listDelNode(l,l->head); //l=listDelNode(l,l->tail); //printf("%d\n",l->len); listRotate(l); //使用void指针的时候需要强制转换 int cc=NULL; listNodetemp=l->tail; while(temp){ cc=(int )(temp->value); printf("%d\n",cc); temp=temp->prev; } / listl2=listDup(l); temp=l2->tail; while(temp){ cc=(int )(temp->value); printf("%d\n",cc); temp=temp->prev; }/ //listSetMatchMethod(l,&intMatch); listNodenode=listIndex(l,1); int zhu=(int)node->value; printf("*zhu:%d\n",*zhu); listRelease(l); //listRelease(l2); system(“pause”); return 0;} ...

删除重复节点，只保留一个示例：Input: 1->1->2Output: 1->2代码：ListNode* deleteDuplicates(ListNode* head) { ListNode pre = head, cur = head; while (cur) { if (pre->val != cur->val) { pre->next = cur; pre = pre->next; } cur = cur->next; } if (pre) pre->next = nullptr; return head;}2. 删除全部重复节点示例：Input: 1->2->3->3->4->4->5Output: 1->2->5代码：ListNode deleteDuplicates(ListNode head) { ListNode *dummy = new ListNode(-1); dummy->next = head; ListNode *pre = dummy, *cur = head; while (cur) { while (cur->next && cur->next->val == cur->val) cur = cur->next; if (pre->next == cur) pre = cur; else pre->next = cur->next; cur = cur->next; } return dummy->next; //不能直接返回 head，因为 head 有可能被删除}

题目输入一个链表，输出该链表中倒数第k个结点。思路简单思路： 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。优化：设定两个节点，间距相差k个节点，当前面的节点到达终点，取后面的节点。前面的节点到达k后，后面的节点才出发。本题目着重考察代码鲁棒性、容错率： 需要考虑head为null，k为0，k大于链表长度的情况代码 function FindKthToTail(head, k) { if (!head || !k) return null; let front = head; let behind = head; let index = 1; while (front.next) { index++; front = front.next; if (index > k) { behind = behind.next; } } return (k <= index) && behind; }

题目描述输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。分析要了解链表的数据结构：val属性存储当前的值，next属性存储下一个节点的引用。要遍历链表就是不断找到当前节点的next节点，当next节点是null时，说明是最后一个节点，停止遍历。最后别忘了，从尾到头遍历链表，不要忘了将你的结果进行翻转。代码/function ListNode(x){ this.val = x; this.next = null;}/function printListFromTailToHead(head){ const result = []; let temp = head; while(temp){ result.push(temp.val); temp = temp.next; } return result.reverse();}拓展链表定义：用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。需要遍历才能查询到元素，查询慢。插入元素只需断开连接重新赋值，插入快。 function LinkList(){ function node(element){ this.value = element; this.next = null; } let length = 0; let head = null; } LinkList.prototype = { // 追加 append:function(element){ var node = new node(element); var temp = this.head; if(this.head){ //遍历找到链表的终点 while(temp.next){ temp = temp.next; } temp.next = node; }else{ this.head = node; } this.length++; }, // 插入 insert:function(element,index){ if(index <= this.length && index>0){ var node = new node(element); var currentIndex = 0; var currentNode = this.head; var preNode = null; if (currentIndex === 0) { node.next = currentNode; this.head = node; return; } while(currentIndex<index){ preNode = currentNode; currentNode = currentNode.next; currentIndex++; } preNode.next = node; node.next = currentNode; this.length++; } } }链表翻转把初始链表头当做基准点移动下一个元素到头部直到下一个元素为空 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } / /* * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { let currentNode = null; let headNode = head; while (head && head.next) { // 将当前节点从链表中取出 currentNode = head.next; head.next = currentNode.next; // 将取出的节点移动到头部 currentNode.next = headNode; headNode = currentNode; } return headNode; }; ...

题目Given a non-empty, singly linked list with head node head, return a middle node of linked list.If there are two middle nodes, return the second middle node.Example 1:Input: [1,2,3,4,5]Output: Node 3 from this list (Serialization: [3,4,5])The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).Note that we returned a ListNode object ans, such that:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.Example 2:Input: [1,2,3,4,5,6]Output: Node 4 from this list (Serialization: [4,5,6])Since the list has two middle nodes with values 3 and 4, we return the second one.Note:The number of nodes in the given list will be between 1 and 100.题目地址讲解一看到这个题目我就知道用快慢指针。但具体操作的时候有些细节需要注意，要让快慢指针指向第0个位置，而不是head（head算作第一个位置）。Java代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode middleNode(ListNode head) { System.out.println(head.val); ListNode slow = new ListNode(0); ListNode fast = new ListNode(0); slow.next = head; fast.next = head; while(slow!=null && fast!=null){ slow = slow.next; if(fast.next!=null){ fast = fast.next.next; }else{ fast = fast.next; } } return slow; }} ...

问题最近研究算法，遇到的一道很有意思的问题——怎么把一个链表反转？很容易想到一个方法：遍历链表，数组作栈存储路径，元素逐个出栈得到的就是反转后的链表！查找资料发现，有更好的方式实现。仔细研究后，终于明白了其中的奥妙。小僧掌握了两种方法，以下分别进行说明。首先给出链表结构：public class LinkedNode { Integer id ; LinkedNode next; public LinkedNode(Integer id) { this.id = id; }}下一步构造出上图的链表结构：LinkedNode node1 = new LinkedNode(1);LinkedNode node2 = new LinkedNode(2);LinkedNode node3 = new LinkedNode(3);LinkedNode node4 = new LinkedNode(4);node1.next = node2;node2.next = node3;node3.next = node4;双指针遍历法先给出代码实现：/** * 链表翻转，循环 + 双指针（pre、next）实现 * @param cur * @return /public LinkedNode reverse(LinkedNode cur){ LinkedNode pre = null; while (cur!=null){ LinkedNode next = cur.next; // 1. cur.next = pre; // 2. pre = cur; // 3. cur = next; // 4. } return pre;}循环体之前，链表示意图：之后进入while循环，注释标注的四个步骤会产生如下变化（图中编号与注释编号一一对应）：第一次循环后，链表变成这样：之后的遍历，链表的变化示意：可见，while循环执行完，pre指向的节点，已经是最新的头节点了！递归法递归的实现方式，似乎更容易理解。/* * 链表反转，递归实现 * @param node * @return */public LinkedNode reverse2(LinkedNode node){ if(node.next==null){ return node; } LinkedNode newHead = reverse2(node.next); node.next.next = node; //node.next.next 换成 newHead.next 不行，因为node在递归中在追溯上一个节点，仔细体会下 node.next = null; return newHead;}首先会通过递归调用找到尾节点，之后做了两件事：尾节点反指 (node.next.next = node;)当前节点指向null节点 (node.next = null;)rentun newHead后，回溯到节点2（此时node就是节点2），再次重复之前的两件事——节点反指和当前节点指向null节点。再次回溯，得到最终的结果。老规矩，完整代码见git：暗夜君王的demo练习——链表反转Done ! ...