代码随想录算法训练营第三天|链表专题一
今日学习任务：
- 链表的理论基础
- 移除链表元素
- 设计链表
- 翻转链表
链表理论基础
什么是链表？
? 链表是一种特殊的线性结构，链表的节点可以分散在内存的各个地方，节点与节点之间通过指针进行连接，通过维护节点和指针指向来管理整个链表。
链表的结构
? 单链表：
? 双链表：
? 循环链表：
链表与数组的区别？
? 链表和数组都是线性结构，数组和链表的结构上的区别在于，数组在内存中是占据一块连续的空间，而链表在内存中的空间是分散开的。由于结构上的不同，导致数组和链表的功能有所差异。
? 对于数组，因为其占据的是一片连续的地址空间，而且可以通过索引下标来访问元素，所以其查询效率是O(1)，而进行插入和删除时，为了保证地址空间连续，所以必须要进行整体移动，效率为O(n)
? 对于链表，节点分散在内存中，节点与节点通过指针连接，并且不具有索引功能，所以我们在查询的时候必须要遍历链表，查询效率为O(n)，在插入和删除时，只需要改变指针之间的连接关系就可以实现插入删除，其效率为O(1)。
? 所以数组和链表的适用场景不同，数组用于查询多，插入删除操作少时，而链表用于查询少，插入删除操作多时，各有各有优点。
链表的代码定义
? 在刷leetcode链表相关算法题时，一般链表结构是已经定义好的，那么如果没有给出链表的结构，就需要我们自己手动去定义链表，因为我学的是Java，下面我给出几种java版本的链表定义。
//单链表
class ListNode<T>{
T val;//节点值，数据类型自己定义
ListNode next; //指向的下一个节点
ListNode(){}//无参构造
ListNode(T val){
this.val=val;
}//有参构造
}
//双链表
class ListNode<T>{
T val;//节点值，数据类型自己定义
ListNode next; //指向的下一个节点
ListNode pre;//指向的上一个节点
ListNode(){}//无参构造
ListNode(T val){
this.val=val;
}//有参构造
}
leetcode 203 移除链表元素
题目链接：https://leetcode.cn/problems/remove-linked-list-elements/
文章链接：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
视频链接：https://www.bilibili.com/video/BV18B4y1s7R9/
题目描述：
? 
思路
? 其实对于链表类题目，算法要求不高，更多是我们处理节点与节点之间关系的能力，考察我们对节点处理的能力。
对于本题，我们只需要从头节点开始遍历链表，如果说遍历到的节点的值等于val的话，那么我们就要删除该节点，那么我们如何进行删除呢？
删除节点首先要知道需要删除节点的前一个节点，让前一个节点的next指向需要删除节点的下一个节点就好了，如上图，我们需要删除D，首先要知道C节点的位置，让C节点的next指向D节点的下一个节点，也就是E节点，这样就完成了删除D节点，在Java中会自动回收D节点，不需要我们手动释放。
对于本题，我们可以使用两种方法来操作链表：
- 使用原链表来进行删除操作。
- 设置虚拟节点进行删除操作。
直接使用原链表操作：
? 当头节点是我们要删除的元素时，就需要单独处理头节点，因为没有前驱节点指向头节点，不然会出现空指针异常。所以需要处理好头节点后在进行操作。
那么头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
通过设置虚拟头节点来解决：
通过虚拟头节点就可以直接操作头节点了，而不需要单独处理，因为头节点也有对应的前驱节点来进行移除。
方法一 ：不使用虚拟头节点
/**
* 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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//不使用虚拟节点的解法
//如果不使用虚拟节点，若头节点就是我们要删除的节点那怎么办呢，我们只要把头节点后移就行了
//处理头节点
while(head!=null && head.val==val){
head=head.next;
}
if(head==null){
return head;
}
//出来之后头节点是一定不等于val的
ListNode pre =head;
ListNode tail=head.next;
while(tail!=null){
if(tail.val==val){
pre.next=tail.next;
tail=pre.next;
}else{
pre=pre.next;
tail=tail.next;
}
}
return head;
}
}
方法二：使用虚拟头节点(推荐！)
/**
* 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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
//使用虚拟节点的解法
if(head==null){
return null;
}
ListNode dummyHead =new ListNode(-1);
dummyHead.next=head;
ListNode pre =dummyHead;
ListNode tail =head;
while(tail!=null){
if(tail.val==val){
pre.next=tail.next;
tail=pre.next;
}else{
pre=pre.next;
tail=tail.next;
}
}
return dummyHead.next;
}
}
leetcode 707 设计链表
题目链接：https://leetcode.cn/problems/design-linked-list/
文章链接：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
视频链接：https://www.bilibili.com/video/BV1FU4y1X7WD/
题目描述：
? 
该题就是单纯的实现给出的五个接口，不涉及算法，考验coding能力。
实现方法有两种，一种是双链表，一种是单链表。
方法一：双链表（自己实现的）
class ListNode{
int val;
ListNode next;
ListNode prev;
ListNode(){
}
ListNode(int val){
this.val=val;
}
}//定义链表
class MyLinkedList {
ListNode head;
ListNode last;
int size;
public MyLinkedList() {
this.size=0;
}
public void print(){
ListNode temp=head;
while(temp!=null){
System.out.print(temp.val+"->");
temp=temp.next;
}
System.out.println("");
}
public int get(int index) {
if(index<0 || index>=size){
return -1;
}
ListNode temp =head;
while(index>0){
temp=temp.next;
index--;
}
return temp.val;
}
public void addAtHead(int val) {
ListNode temp =new ListNode(val);
//如果链表为空，新添的节点就初始化为头节点和尾节点
if(head==null){
temp.next=null;
temp.prev=null;
head=temp;
last=temp;
}else{
temp.next=head;
temp.prev=null;
head.prev=temp;
head=temp;
}
size++;
}
public void addAtTail(int val) {
//如果链表为空，新添的节点就初始化为头节点和尾节点
ListNode temp =new ListNode(val);
if(head==null || last==null){
temp.next=null;
temp.prev=null;
head=temp;
last=temp;
}else{
last.next=temp;
temp.prev=last;
temp.next=null;
last=temp;
}
size++;
}
public void addAtIndex(int index, int val) {
if(index==size){
addAtTail(val);
}else if(index<=0){
addAtHead(val);
}else if(index>size){
return;
}else{
ListNode temp =head;
while(index>0){
temp=temp.next;
index--;
}
ListNode new_node =new ListNode(val);
ListNode pre_node=temp.prev;
pre_node.next=new_node;
new_node.next=temp;
temp.prev=new_node;
new_node.prev=pre_node;
size++;
}
}
public void deleteAtIndex(int index) {
if(index<0 || index>=size){
return;
}
if(index==0){
head=head.next;
size--;
return;
}
if(index==size-1){
last=last.prev;
size--;
return;
}
ListNode temp =head;
while(index>0){
temp=temp.next;
index--;
}
ListNode pre_node =temp.prev;
ListNode next_node=temp.next;
pre_node.next=next_node;
next_node.prev=pre_node;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
方法二：单链表（搬运卡哥的）
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
int size;
//虚拟头结点
ListNode head;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//获取第index个节点的数值
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
//找到要插入节点的前驱
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
//删除第index个节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
if (index == 0) {
head = head.next;
return;
}
ListNode pred = head;
for (int i = 0; i < index ; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
leetcode 206 翻转链表
题目链接：https://leetcode.cn/problems/reverse-linked-list/
文章链接：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
视频链接：https://www.bilibili.com/video/BV1nB4y1i7eL/
题目详情：
思路
因为题目没有要求只能在原地修改，所以我们可以通过遍历链表，然后创建一个新的链表使用头插法，即可实现，但这样就失去了题目的意义，所以我们提高点难度，只能在原地修改链表。
假设原链表为1->2->3->4->5，将其反转后就是 5->4->3->2->1
我们在反转链表的时候，得需要知道前一个节点，这样将当前链表的next执行前一个节点，然后应该怎么办，是不是两个节点都要往后移动，这样才能让下一个节点也反转，所以我们是不是在反转前，得把当前节点的后一个节点保存下来，这样当你反转完后，才能将两个节点顺利后移。
可能表达的不是很清晰，所以我们看代码：
方法一：双指针法（两个节点往后遍历法）
/**
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//如果头节点为空就没必要反转了，直接返回
if(head==null){
return head;
}
//双指针法，两个节点，一个指向null,一个指向head
ListNode pre =null;
ListNode tail=head;;
//结束条件，当最后一个节点反转之后,temp指向的是null,而tail=temp=null，所以结束条件就是 tail=null
while(tail!=null){
//保存当前节点的后一个节点
ListNode temp=tail.next;
//反转，将当前节点指向前一个节点
tail.next=pre;
//将前一个结点赋值为当前节点
pre=tail;
//将当前节点赋值为后一个节点
tail=temp;
//这样子，就保证了顺利遍历整个链表，而且每次反转的时候都知道前一个节点和后一个节点的位置
}
//结束之后，pre节点移动到末尾，也就是反转后的头节点
return pre;
}
}
方法二：递归法（简易版双指针法，原理相同）
//在我看来，递归就是把一直反转的操作抽取出来，每次传入两个节点，让其反转就好了
/**
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
//递归法，head相当于当前节点，Null为反转后指向的前一个节点
return reverse(null,head);
}
public ListNode reverse(ListNode pre,ListNode cur){
//递归结束条件，与双指针法一样
if(cur==null){
return pre;
}
//保存当前节点的下一个节点
ListNode temp=cur.next;
//真正的反转操作
cur.next=pre;
//递归，在这里就是，传入需要反转的节点以及前一个节点
//cur相当于是下一次反转的前一个节点，temp相当于是下一次反转的当前节点
return reverse(cur,temp);
}
}
一入递归深似海，从此offer是路人，泪…
Carl YYDS！