Linkedlist

用JavaScript实现基于对象的单项链表单向链表介绍何为单向链表 与数组的索引: 值（可以直接在数组层面对值进行修改）不同，链表各个值的关系偏向去中心化。 见上图，每个节点可分为两部分：1. 节点的值；2. 下一个节点的指向，即下一个节点是谁。例如：上图链表中的第一个节点，它的值是milk，它的下一个节点是值为Bread的节点。 单向链表优点当我们需要组织数据时，数组不总是最佳的数据结构（对于大多数编程语言而言），缘于它有两个显著的缺点：1. 数组的长度是固定的，当数组已被数据填满时，加入新数据会显得很麻烦；2. 当我们插入、或删除数组中的某个值时，需要把数组中的其它值向后、或向前移动，以反映数组被进行了增删操作。 所以当我们需要频繁的对数据进行增删操作时，选择数组不是那么地明智，这时我们可以使用链表来实现对数据的增删功能。链表的增删会方便很多，当增加数据时，只需要更改它的节点指向和上一级节点的节点指向；当删除数据时，只需把待删除节点的节点指向赋给上一级节点即可，此时待删除节点便在链表中消失了（因为无法通过节点与节点的关系再找到它，便可视为消失了）。 例如：如果我们在milk和bread中增加sandwich数据，只需把milk的节点指向改为sandwich，把指向bread的节点指向赋给sandwich即可；当需要删除sandwich时，只需把指向bread的节点指向赋给milk即可，此时sandwich便自动消失了。 构建链表当我们需要组织某一类的数据时，只需先建一个相应的构造器（构造函数）即可，这个构造器应包含以下的属性和方法：头节点；增，删，查等。 节点构造器我们可以先做头节点的构造器； //我们可以把一个节点视为一个盒子，这个盒子被分为两部分，一部分盛放的是该节点的值，另一部分盛放的则是指向下一个节点的节点指向。function Node(element) { this.element = element; this.next = null;}链表构造器某类数据的链表构造器 function LList() { //LList: linkedList链表 //新建值为head的节点（表头），便可一生二二生三三生万物了，下面的操作都要基于表头。 this.head = new Node("head"); //查找方法，给find一个值，便可查到相应的节点 this.find = find; //插入方法，可以实现在哪插入、插入什么数据的功能 this.insert = insert; //展示打印功能，传入想要查询的节点的元素，该节点便能被打印出来，包括的指向的下一节点 this.display = display; //如果要删除某一节点，则需要找到它的前一节点，修改它的节点指向 this.findPrevious = findPrevious; //删除方法，传入想要删除的元素，即可实现删除功能 this.remove = remove; }find()方法find()方法展示了如何在链表上进行移动。首先，新创一个节点，并将表头赋给这个新创的节点。然后在链表上进行循环，如果如果当前节点的element属性和我们要查找的值不一样，就从当前节点移到下一节点，如果查找成功，返回包含该数据的节点，失败，返回null。 function find(item) { //将表头赋给新创的节点 var currNode = this.head; //循环，如果当前节点的值与我们想要查找的值不一样，移动到下一节点。知道找到目标或移到null while (currNode.element !== item) { currNode = currNode.next; } //返回相应节点或null return currNode;}insert()方法insert()实现插入功能，传入新节点的值newElement和待插位置item，并修改新节点和待插位置的节点指向，完成插入。 ...

前言前不久帮同事一起 review 一个 job 执行缓慢的问题时发现不少朋友在撸码实现功能时还是有需要细节不够注意，于是便有了这篇文章。 ArrayList 踩坑List<String> temp = new ArrayList() ;//获取一批数据List<String> all = getData();for(String str : all) { temp.add(str);}首先大家看看这段代码有什么问题嘛？ 其实在大部分情况下这都是没啥问题，无非就是循环的往 ArrayList 中写入数据而已。 但在特殊情况下，比如这里的 getData() 返回数据非常巨大时后续 temp.add(str) 就会有问题了。 比如我们在 review 代码时发现这里返回的数据有时会高达 2000W，这时 ArrayList 写入的问题就凸显出来了。 填坑指南大家都知道 ArrayList 是由数组实现，而数据的长度有限；需要在合适的时机对数组扩容。 这里以插入到尾部为例 add(E e)。 ArrayList<String> temp = new ArrayList<>(2) ;temp.add("1");temp.add("2");temp.add("3");当我们初始化一个长度为 2 的 ArrayList ，并往里边写入三条数据时 ArrayList 就得扩容了，也就是将之前的数据复制一份到新的数组长度为 3 的数组中。 之所以是 3 ，是因为新的长度=原有长度 * 1.5通过源码我们可以得知 ArrayList 的默认长度为 10. 但其实并不是在初始化的时候就创建了 DEFAULT_CAPACITY = 10 的数组。 ...

题目要求You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.Follow up:What if you cannot modify the input lists? In other words, reversing the lists is not allowed.Example:Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7对以链表形式的两个整数进行累加计算。 ...

什么是LinkedList1 LinkedList 是一个 Doubly-linked list双向连表，实现了Deque接口，该接口中定义了双向连表的一般操作。 2 LinkedList 也实现了List接口，所以List包含的基本方法（新增，删除，插入等）LinkedList都实现了。 3 LinkedList 也继承了AbstractSequentialList该类中定义了顺序访问所需实现的方法。 顺序访问：数据是有序的，访问也是有序的，获取元素必须从头开始遍历比对，不能直接以数组的方式获取指定索引位上的值。随机访问：随机访问可以通过随机访问方法直接获取指定索引位上的值如ArrayList的get(int index), set(int index, E element), add(int index, E element) and remove(int index)等 双向连表数据结构及相关操作1.基本结构 双向连表包含的基本元素包含直接前驱、直接后继、值域，直接前驱指向前一个节点地址，直接后继指向后一个节点地址，直接前驱为空时是头节点，直接后继为空时是尾节点 2.基本操作(add,remove过程相反) 在双向连表中插入节点时需要改变插入位置前后两个节点的直接前驱和直接后继的指向如图所示 LinkedList的实现LinkedList 在内部是通过一个私有的静态内部类来实现连表的，内部类代码如下 transient Node<E> first; // 头节点transient Node<E> last; // 尾节点private static class Node<E> { // 存放数据 E item; // 直接后继 Node<E> next; // 直接前驱 Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}LinkedList的操作都是围绕着first last这两个对象来进行。 ...

ProblemGiven a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.Example 1:Input: 1->2->3->4->5->NULLOutput: 1->3->5->2->4->NULLExample 2:Input: 2->1->3->5->6->4->7->NULLOutput: 2->3->6->7->1->5->4->NULLNote:The relative order inside both the even and odd groups should remain as it was in the input.The first node is considered odd, the second node even and so on …Solutionclass Solution { public ListNode oddEvenList(ListNode head) { if (head == null) return head; ListNode odd = head, even = head.next, evenHead = even; while (even != null && even.next != null) { odd.next = odd.next.next; even.next = even.next.next; odd = odd.next; even = even.next; } odd.next = evenHead; return head; }} ...

ProblemGiven 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.SolutionSOL.1class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; }}SOL.2class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head, slow = head; int n = 1; while (fast.next != null) { fast = fast.next; n++; } int k = n/2; while (k != 0) { slow = slow.next; k–; } return slow; }} ...

ProblemGiven a linked list, rotate the list to the right by k places, where k is non-negative.Example 1:Input: 1->2->3->4->5->NULL, k = 2Output: 4->5->1->2->3->NULLExplanation:rotate 1 steps to the right: 5->1->2->3->4->NULLrotate 2 steps to the right: 4->5->1->2->3->NULLExample 2:Input: 0->1->2->NULL, k = 4Output: 2->0->1->NULLExplanation:rotate 1 steps to the right: 2->0->1->NULLrotate 2 steps to the right: 1->2->0->NULLrotate 3 steps to the right: 0->1->2->NULLrotate 4 steps to the right: 2->0->1->NULLSolutionclass Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy, slow = dummy; int n = 0; while (fast.next != null) { fast = fast.next; n++; } k = n-k%n; while (k > 0) { slow = slow.next; k–; } fast.next = dummy.next; dummy.next = slow.next; slow.next = null; return dummy.next; }} ...