|
#Java、#链表
一、今日学习链接
????????文章链接：1、https://www.programmercarl.com/链表理论基础.html#单链表????
? ? ? ? ? ? ? ? ? ? ? ? ? ?2、https://www.programmercarl.com/0203.移除链表元素.html#其他语言版本
? ? ? ? ? ? ? ? ? ? ? ? ? ?3、https://www.programmercarl.com/0707.设计链表.html#代码
? ? ? ? ? ? ? ? ? ? ? ? ? ?4、https://www.programmercarl.com/0206.翻转链表.html????????
? ? ? ? 视频链接：1、L203.移除链表元素
? ? ? ? ? ? ? ? ? ? ? ? ? ?2、L707.设计链表
? ? ? ? ? ? ? ? ? ? ? ? ? ?3、L206.反转链表
二、链表理论基础（摘自上述文章链接）
????????链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
? ? ? ? 链表的类型：单链表、双链表。单链表中的指针域只能指向节点的下一个节点。双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双链表 既可以向前查询也可以向后查询。循环链表，顾名思义，就是链表首尾相连。可以用来解决约瑟夫环问题。
? ? ? ? 链表的存储方式：数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
? ? ? ? 性能分析：数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
| 插入/删除（时间复杂度） | 查询（时间复杂度） | 适用场景 | | 数组 | O(n) | O(1) | 数据量固定，频繁查询，较少增删 | | 链表 | O(1) | O(n) | 数据量不固定，频繁增删，较少查询 |
三、解题思路
| 题号 | 思路 | 相关主题 | 难度 | | 203.?Remove Linked List Elements | dummy node: dummy, prev, head, cur while(cur != null) 考虑当头节点就是要删除元素的情况 | 删除链表 | easy | | 707.?Design Linked List | singly linked list (contstructor) 全局变量：size, head 方法一：不使用dummy node，不调用addAtIndex 方法二：使用dummy node，调用addAtIndex | 设计链表 | medium | | 206.?Reverse Linked List | prev, cur, cur.next while(cur != null) return prev; 反转链表不需要dummy | 反转链表 | easy |
//707. Design Linked List
//不使用dummy node
//Single LinkedList Define
class ListNode {
int val;
ListNode next;
ListNode() {};
ListNode(int val){
this.val = val;
}
ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
//MyLinkedList
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
this.size = 0;
this.head = null;
}
public int get(int index) {
if(index < 0 || index >= this.size) {
return -1;
}
ListNode cur = head;
int count = 0;
while(count != index){
cur = cur.next;
count++;
}
return cur.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
public void addAtTail(int val) {
if(this.size == 0) {
addAtHead(val);
return;
}
ListNode newNode = new ListNode(val);
ListNode temp = head;
while(temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = null;
this.size++;
}
public void addAtIndex(int index, int val) {
if(index == 0) {
addAtHead(val);
return;
}
if(index > this.size) {
return;
}
if(index == this.size) {
addAtTail(val);
return;
}
ListNode newNode = new ListNode(val);
ListNode cur = head;
int count = 0;
while(count != index-1) {
cur = cur.next;
count++;
}
newNode.next = cur.next;
cur.next = newNode;
this.size++;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= this.size) {
return;
}
ListNode cur = head;
if(index == 0) {
head = cur.next;
this.size--;
} else {
ListNode prev = null;
int count = 0;
while(count != index){
prev = cur;
cur = cur.next;
count++;
}
prev.next = cur.next;
this.size--;
}
}
}
//707. Design Linked List
//使用dummy node
//singly LinkedList
class ListNode {
int val;
ListNode next;
ListNode(){};
ListNode(int val){
this.val = val;
}
ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);//dummy
}
public int get(int index) {
if(index < 0 || index >= size){
return -1;
}
ListNode cur = head;
for(int i=0; i<=index; i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if(index > size){
return;
}
if(index < 0) {
index = 0;
}
size++;
ListNode newNode = new ListNode(val);
ListNode cur = head;
for(int i=0; i<index; i++){
cur = cur.next;
}
newNode.next = cur.next;
cur.next = newNode;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) {
return;
}
size--;
ListNode cur = head;
for(int i=0; i<index; i++){
cur = cur.next;
}
cur.next = cur.next.next;
}
}
四、总结
? ? ? ? 链表的设计思路：借助后向指针（next）组织数据。链表是为了解决动态数量的数据存储问题而发明的。更优方案：二叉树、满二叉树、平衡树、红黑树。
|