文章目录

• • 一、面试中链表的基本知识
  • • 什么是链表
    • 链表的分类
    • 链表的存储方式
    • 链表的定义
    • 链表的操作
  • 二、移除链表元素
  • • 双指针思路
    • AC代码
    • 递归思路
    • AC代码
  • 三、设计链表
  • • 思路
    • AC代码
  • 四、反转链表
  • • 思路
    • AC代码
  • 关于解题是不是用虚拟节点

一、面试中链表的基本知识

什么是链表

定义：链表就是一种通过“指针”连在一起的线性结构。每个节点由由两部分组成，一个是数据域，一个是指针域。数据域中存放的是下一个节点的地址，最后一个节点的指针域指向null。但是具体数据域中是不是只有一个数据，指针域中只有一个指针，这个我们并没有规定。

链表的分类

根据方向分：单向、双向

根据循不循环分：循环，非循环

根据带不带头分：带头、不带头

所以总共有2^3种，但是并不是全部都常用。比较常用的是无头非循环单链表、无头 非循环双链表等。

链表的存储方式

先说结论：在内存中不是连续存储的。

链表是通过指针域的指针链接在内存中的各个节点，是散乱分布在内存的某些地址上，但是也有一定的概率连续存储。也可以说是链表的节点在内存中是随机存储的，可连续可不连续。

链表的定义

先说一下大体思路。定义一个链表结构，我们首先需要有一个链表节点，这个节点结构的定义在java中我们一般单独写一个类。对于链表，内部我们需要实现它的操作。至于这个节点类我们写在内部写在外部都可以，只不过如果是写成MyLinkedList的内部类，再测试类中调用的时候可能相对比较麻烦。下边我们写一下大概的轮廓。

class ListNode{int val;ListNode next;public ListNode(int val){this.val=val;}
}
class MyLinkedList {int size;ListNode head;public MyLinkedList() {size=0;head=new ListNode(0);}/***之后定义一些操作*/
}

这里我将它写成了外部类。

同时注意MyLinkedList应该怎么构造？

定义类属性size和head，在构造方法中赋值，如果想要虚拟头，就给head赋值为-1或者0,想要不带头的直接赋成null。

链表的操作

1. 删除节点

​ 一般需要用到双指针，或者直接cur.next=cur.next.next;

2. 增加节点

   头插尾插不需要双指针，中间插入需要用到双指针。

3. 查找节点

   直接遍历

4. 更改节点值

   遍历更改

​ ……

二、移除链表元素

题目链接

双指针思路

比较简单的一种方法，定义虚拟头结点

1. 双指针pre和cur
2. 定义临时变量curNext记录cur的下一个节点
3. 如果是cur是需要删除的节点
4. curNext始终指向cur的下一个节点
5. pre和curNext连接
6. cur变成null，遍历结束

AC代码

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode tmp=new ListNode(-1);tmp.next=head;ListNode pre=tmp;ListNode cur=head;while(cur!=null){ListNode curNext=cur.next;if(cur.val==val){pre.next=cur.next;}else{pre=cur;}          cur=curNext;}return tmp.next;}
}

递归思路

直接双指针改递归即可

AC代码

class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null){return head;}ListNode newHead=reverseList(head.next);head.next.next=head;head.next=null;//一定注意这两个顺序return newHead;}
}

三、设计链表

题目链表

思路

注意MyLinkedList构造方法怎么写

1. MyLinkedList构造方法:在外部定义size和head，在内部进行初始化
2. get:首先判断index是否合法，注意到底循环多少次(index是从0开始的)
3. addAtHead、addAtTail都是基于addAtIndex完成的。addAtIndex也是需要判断坐标是否合法的，但是注意，他这里有个特殊处理，就是如果给定的坐标如果是负数，全部插入到0位置。这个跟我以前实现的是不一样的。
4. 删除指定下标的元素，首先判断坐标是否合法，之后找到需要删除的元素。但是这里没有用双指针而是直接通过pre.next=pre.next.next;完成的。

之前我也写了关于链表的总结，里边也有对无头非循环单链表的实现，那里边相对这里有些区别，比如说指定坐标插入元素时基于头插和尾插实现的，还有坐标合法性的判断，如果是负数，直接判定不合法，再比如节点是写成了内部类等等。

但无论哪种写法都是特别注意循环条件的判断到底是cur.next还是cur不为空以及插入节点的时候一定要先绑定后边的！！！。

AC代码

class ListNode{int val;ListNode next;public ListNode(int val){this.val=val;}
}
class MyLinkedList {int size;ListNode head;public MyLinkedList() {size=0;head=new ListNode(0);}public int get(int index) {if(index<0||index>=size){return -1;}ListNode cur=head;while(index+1!=0){cur=cur.next;index--;}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 ;}index=Math.max(0,index);size++;ListNode pre=head;while(index--!=0){pre=pre.next;}ListNode node=new ListNode(val);node.next=pre.next;pre.next=node;}public void deleteAtIndex(int index) {if(index<0||index>=size){return ;}size--;ListNode pre=head;while(index--!=0){pre=pre.next;}pre.next=pre.next.next;}
}

四、反转链表

题目链接

思路

1. 定义遍历变量cur，定义临时变量curNext,始终指向cur的下一个节点
2. 每次更改head的next域
3. cur为空，结束循环
4. 返回head

AC代码

class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;cur.next=head;head=cur;cur=curNext;}return head;}
}

关于解题是不是用虚拟节点

一般而言我用的不是特别多。但是对于特征比较明显的有时候会用，比如这里的删除元素。但是目前不用，其实也可以锻炼解题思维。不做强制要求。

关于链表的设计构造方法可以初始成带头的，也可以初始化成不带头的。

基本上所有的链表题目，都可以采用使用头结点和不适用头结点，看个人喜好了。