大连百度关键词排名_漳州seo建站_专业软文发布平台_公司的网站制作

---

1. ArrayList的缺陷

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链式结构在逻辑上是连续的，但是在物理上不一定连续。

链表是一个一个的称为 节点的对象组成的。这个节点至少有两个域，一个是value域（用来存放数据的），还有一个叫做next域（存放节点对象的地址）。

链表共有八种数据结构：

1. 单向或者双向
   
2. 带头或不带头
   
3. 循环或非循环
   
   重点掌握的两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  
• 无头双向链表： 在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

public class MySingleList {static class ListNode{public  int value;public ListNode next;//构造方法public ListNode(int value){this.value = value;}}public ListNode head;/*** 链表的创建*/public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;}/*** 链表的遍历** 问：为什么不直接让head走，而是定义一个中间变量cur呢？* 答：如果直接使用head来遍历链表的话，我们的head在遍历一次之后就走到了链表的尾端，*     就不能再次进行遍历了，就相当于head的这个信息就不存在了*/public void show(){ListNode cur = head;while (cur != null){System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}/*** 求链表的长度* @return*/public int size(){int count = 0;ListNode cur = head;while (cur != null){count++;cur = cur.next;}return count;}/*** 是否包含数据key* @param key  要查找的元素* @return  返回是否找到*/public boolean contains(int key){ListNode cur = head;while (cur != null){if (cur.value == key){return true;}cur = cur.next;}return false;}/*** 头插法* @param data*/public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}/*** 尾插法* @param data*/public void addLast(int data){ListNode node = new ListNode(data);//head为空if (head == null){head = node;return;}//1. 找尾巴ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = node;}/*** 在任意位置插入一个节点** 1. index = 0，头插法* 2. index = len，尾插法* 3. 找到index的位置的前一个节点* 4. 开始进行插入* @param index* @param data*/public void insertNode(int index, int data){if (index < 0 || index > size()){return;}if (index == 0){addFirst(data);}else if (index == size()){addLast(data);}else {ListNode node = new ListNode(data);ListNode cur = finIndex(index);node.next = cur.next;cur.next = node;}}/*** 找到index位置的前一个节点* @param index* @return*/private ListNode finIndex(int index){ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}return cur;}/*** 删除第一个出现关键字key的节点** 1. cur要走到删除节点的前一个节点的位置* @param key*/public void remove(int key){//链表为空if (head == null){return;}//要删除的节点为头节点if (head.value == key){head = head.next;return;}ListNode cur = findKey(key);//没有要删除的数据if (cur == null){return;}//删除节点cur.next = cur.next.next;}/*** 找到要删除的key的前一个节点* @param key * @return*/public ListNode findKey(int key){ListNode cur = head;while (cur.next != null){if (cur.next.value == key){return cur;}cur = cur.next;}return null;//没有找到返回nul}/*** 删除所有的关键字key的节点* @param key*/public void removeAllKey(int key){//链表为空if (head == null){return;}ListNode cur = head.next;ListNode prev = head;while (cur != null){if (cur.value == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if (head.value == key){head = head.next;}}/*** 要实现每一个节点的内存得到回收* 1. head = null* 2. 将每个节点的next域和value域都置为空*/public void clear(){ListNode cur = head;while (cur != null){ListNode curN = cur.next;cur.next = null;cur = curN.next;}head = null;}
}

3. 链表面试题

3.1 移除链表元素

在线oj

class Solution {public ListNode removeElements(ListNode head, int val) {while(head != null && head.val == val){head = head.next;}if(head == null) return null;ListNode cur = head.next;ListNode prev = head;while(cur != null){if(cur.val == val){cur = cur.next;prev.next = cur;}else{prev = cur;cur = cur.next;    }}return head;}
}

3.2 反转链表

在线oj

这里的链表反转是指链表的结构反转。

/**利用链表的头插法*/
class Solution {public ListNode reverseList(ListNode head) {if (head == null){return null;}ListNode cur = head.next;head.next = null;while (cur != null){ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;}
}

3.3 链表的中间结点

在线oj

解法一（遍历链表两遍）：

1. 求链表的长度len
2. 走len/2步

解法二：快慢双指针算法（只遍历链表一遍）
fast走两步，slow走一步。

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

3.4 返回链表的倒数第k个节点

在线oj

解题思路：

1. fast = head，slow = head
2. fast走k-1步
3. fast 和 slow一起往前走，fast走到链表的尾时，slow所指向的位置就是倒数第k个节点的位置。

class Solution {public int kthToLast(ListNode head, int k) {if (k <= 0){return -1;}ListNode fast = head;ListNode slow = head;for (int i = 0; i < k-1; i++) {if (fast == null){return -1;}fast = fast.next;}while (fast.next != null){fast = fast.next;slow = slow.next;}return slow.val;}
}

3.5 合并两个有序链表

在线oj

解题思路：

1. 定义一个傀儡结点newH
2. 定义headA、headB两个结点分别指向两个链表的头。
3. 比较headA.value 和 headB.value的大小
   

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode();ListNode tempH = newHead;while (list1 != null && list2 != null){if (list1.val < list2.val){tempH.next = list1;tempH = tempH.next;list1 = list1.next;}else {tempH.next = list2;tempH = tempH.next;list2 = list2.next;}}//拼接上去没有走完的链表if (list1 != null){tempH.next = list1;}if (list2 != null){tempH.next = list2;}return newHead.next;}
}

3.6 链表分割

在线oj
描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereListNode cur = pHead;ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;while (cur != null){if (cur.val < x){if (bs == null){bs = cur;be = cur;}else {be.next = cur;be = be.next;}}else {if (as == null){as = cur;ae = cur;}else {ae.next = cur;ae = ae.next;}}cur = cur.next;}if (bs == null){return as;}if (as != null){ae.next = null;}be.next = as;return bs;}
}

3.7 链表的回文结构

在线oj

解题思路:

1. 找到中间结点
2. 反转中间结点以后的链表
3. head —> <—slow

public class PalindromeList {public boolean chkPalindrome(ListNode head) {if (head == null){return false;}//1. 找到中间结点ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}//2. 反转中间节点之后的数据ListNode cur = slow.next;while (cur != null){ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//3. 判断是否是回文结构while (head != slow ){if (head.val != slow.val){return false;}if (head.next == slow){return true;}head = head.next;slow = slow.next;}return true;}
}

3.8 相交链表

在线oj

解题思路：

1. 求2个链表的长度lenA lenB
2. 根据链表的长度确定哪个链表长，长的链表用pl指向，短的链表用ps指向
3. 让长的链表先走差值步，len =Math.abs(lenA-lenB)pl走
4. 一起走，下次相遇之后就是交点

public class Solution {public int length(ListNode head){ListNode cur = head;int count = 0;while (cur != null){count++;cur = cur.next;}return count;}public ListNode getIntersectionNode(ListNode headA, ListNode headB){//1. 求两个链表的长度，假设A链表最长int lenA = length(headA);int lenB = length(headB);//2. 根据链表的长度 确定pl ps 的指向if (lenA > lenB){ListNode pl = headA;ListNode ps = headB;//3. 让pl先走length= pl-ps步for (int i = 0; i < Math.abs(lenA-lenB); i++) {pl = pl.next;}//4. pl ps 一起往前走，直到相遇while (pl != null && ps != null){if (pl == ps){return ps;}ps = ps.next;pl = pl.next;}return null;}else {ListNode pl = headB;ListNode ps = headA;//3. 让pl先走length= pl-ps步for (int i = 0; i < Math.abs(lenA-lenB); i++) {pl = pl.next;}//4. pl ps 一起往前走，直到相遇while (pl != null && ps != null){if (pl == ps){return ps;}ps = ps.next;pl = pl.next;}return null;}}
}

3.9 环形链表

在线oj

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
• 快指针一次走3步，走4步，…n步行吗？

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow){return true;}}return false;}
}

3.10 环形链表II

在线oj

结论：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇
证明：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow){break;}}if (fast == null || fast.next == null){return null;}fast = head;while (fast != slow){fast = fast.next;slow = slow.next;}return fast;}
}