目录
链表是有序的链表，具有以下特点：
1）链表是以节点的方式来存储，是链式存储
2）每个节点包含data域，next域：指向下一个节点
3）链表的各个节点不一定是连续存储。
4）链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
一般啥时候用带头节点，啥时候不用带头节点？
一、不带头的单链表
不带头节点的单链表操作中，除了初始化、删除和插入操作与带头结点的单链表有差别外，其它的操作基本都一样。除了插入，删除，清空操作需要传递头指针的地址外，其他基本一样。
基本操作
public class SingleLinkedList {
private int size;//节点个数
private Node head;//头节点
/**
* 在链表头部添加一个元素
* @param val
*/
public void addFirst(int val){
//新建节点表示待添加的节点
Node node = new Node(val);
if(head == null){
head = node;
}else{
node.next = head;
head = node;
}
size++;
}
/**
* 在单链表的任意一个索引位置插入元素val
* @param index
* @param val
*/
public void addIndex(int index,int val){
//1.判断合法性
if(index < 0 || index > size){//此时size位置是合法的，表示尾插。
System.err.println("add index illegal!");
}
//2.头插
if(index == 0){
addFirst(val);
return;
}
//3.插入元素
Node node = new Node(val);
//3.1找到待插入位置的前驱,从头节点开始向后依次走index - 1步
Node prev = head;
for(int i = 0; i < index - 1;i++){
prev = prev.next;
}
//3.2此时prev指向待插入位置的前驱节点
node.next = prev.next;
prev.next = node;
size++;
}
/**
* 在单链表的尾部插入元素
* @param val
*/
public void addLast(int val){
addIndex(size,val);
}
/**
* 根据用户输入的index查找对应值
* @param index
* @return
*/
public int get(int index){
//1.合法性判断
if(index < 0 || index >= size){//此时size位置是非法的,index + 1 == size
System.err.println("get index illegal");
}
//从头节点开始遍历链表,走到index位置
//创建临时节点辅助遍历
Node temp = head;
//2.找到index
for(int i = 0;i < index;i++){
temp = temp.next;
}
return temp.val;
}
/**
* 判断当前链表中是否包含值为val的节点
* @param val
* @return
*/
public boolean contains(int val){
//遍历整个链表
//定义一个辅助节点帮助遍历
Node temp = head;
while(temp != null){
if(temp.val == val){
return true;
}
temp = temp.next;//temp后移,遍历整个链表
}
return false;
}
/**
* 将单链表中索引为index的节点值改为newVal
* @param index
* @param newVal
* @return 修改前的值
*/
public int set(int index,int newVal){
//合法性判断
if(index < 0 || index >= size){//此时size位置是合法的,index + 1 == size
System.out.println("set index illegal!");
return -1;
}
Node temp = head;
//遍历链表,找到index
for(int i = 0;i < index;i++){
temp = temp.next;
}
//修改
int oldVal = temp.val;
temp.val = newVal;
return oldVal;
}
/**
* 删除指定index的节点
* @param index
*/
public void removeIndex(int index){
//1.合法性判断
if(index < 0 || index >= size){//此时size位置是合法的,index + 1 == size
System.err.println("index illegal!");
return;
}
//2.判断头节点
if(head != null && index == 0) {
// //我的写法：测试正确
Node temp = head;
head = temp.next;
temp.next = null;
//正解：
// Node temp = head;
// head = head.next;
// temp.next = null;
size--;
}else{
//此时的index是中间位置
//3.遍历找到index的【前驱节点】并删除index
//定义一个辅助节点temp帮助遍历
Node prev = head;
for(int i = 0;i < index - 1;i++){
prev = prev.next;
}
//方式一：cur:待删除节点
// Node cur = prev.next;
// prev.next = cur.next;
// cur.next = null;
//方式二：
prev.next = prev.next.next;
size--;
}
}
/**
* 删除第一个节点
*/
public void removeFirst(){
removeIndex(0);
}
/**
* 删除最后一个节点
*/
public void removeLast(){
removeIndex(size - 1);
}
/**
* 找到值为val的第一个节点并删除
* @param val
*/
public void removeValueOnce(int val){
//1.遍历链表,找到值为val的节点-> 不知道值为val的节点在哪个位置
//找到后删除(正常的删除都需要找到前驱,只有头节点没有前驱)
if(head != null && head.val == val){
Node temp = head;
head = head.next;
temp.next = null;
size--;
}else{//2.else【要删除的节点是中间节点,一定不是头节点】
Node prev = head;
//超级重点：看你取值用的是那个引用,就判断那个引用不为空
while(prev.next != null){
if(prev.next.val == val){
prev.next = prev.next.next;//删除prev.next
size--;
return;
}
prev = prev.next;//后移,prev不是待删除节点的前驱
}
}
}
/**
* 找到值为val的所有节点并删除
*
* 这个方法挺难写的,有许多小细节！！！！
* @param val
*/
public void removeValueAll(int val){
//1.判断头节点是否是待删除节点
//注意：要用while循环删除,因为删除头节点后,头节点会更新
while(head != null && head.val == val){
Node temp = head;
head = head.next;
temp.next = null;
size--;
}
if(head == null){
//此时链表中的值全是val
return;
}else{//2.else【index为中间节点,一定不是head】
//遍历找到所有满足val的前驱节点,并删除前驱节点的下一个节点
Node prev = head;
while(prev.next != null){
if(prev.next.val == val){
prev.next = prev.next.next;//删除
size--;
}else{
prev = prev.next;
}
}
}
}
/**
* 找到值为val的所有节点并删除
* leetcode203题：给定一个头节点为head的链表,删除该链表中
* 所有值为val节点并返回删除后的头节点
*
* 递归版,超级难理解！！！
* @param val
*/
public Node removeValueAll(Node head,int val){
//递归出口
if(head == null){
return null;
}
//将head.next以及之后的节点处理不了,交给removeValueAll(head.next,val)
head.next = removeValueAll(head.next,val);
//自己处理下头节点
if(head.val == val){
return head.next;
}
return head;
}
public String toString(){
String res = "";
//遍历链表
//从头节点开始至尾节点
//暂时存储当前头节点地址
Node node = head;
while(node != null){
res += node.val;
res += "->";
//继续访问下一个节点
node = node.next;
}
res += "NULL";
return res;
}
}
class Node{
int val;//存储具体数据
Node next;//保存下一个节点的地址
public Node(int val) {
this.val = val;
}
}
删除操作中的重点
/**
* 找到值为val的所有节点并删除
* leetcode203题：给定一个头节点为head的链表,删除该链表中
* 所有值为val节点并返回删除后的头节点
*
* 递归版,超级难理解！！！
* @param val
*/
public Node removeValueAll(Node head,int val){
//递归出口
if(head == null){
return null;
}
//将head.next以及之后的节点处理不了,交给removeValueAll(head.next,val)
head.next = removeValueAll(head.next,val);
//自己处理下头节点
if(head.val == val){
return head.next;
}
return head;
}
二、带头节点的单链表
在单链表的中间位置插入和删除元素时,都需要找到待处理位置的前驱prev
但是头节点没有前驱,都需要把头节点特殊处理
=> 将所有节点一视同仁(所有节点一定都有前驱) -> 不用处理头节点
=> 虚拟节点(这个节点不存储具体值,只是作为链表的头部)
虚拟头节点的值一般是链表要存储数据范围之外的值
/**带头单链表
* @author zx
* @create 2021-12-03 14:13
*/
public class SingleLinkedListWithHead {
//当前存储的元素个数
private int size;
//虚拟头节点
private Node dummyHead = new Node(-1);
/**
* 在指定index处添加节点
* @param index
* @param val
*/
public void addIndex(int index,int val){
//判断index的合法性
if(index < 0 || index > size){//此时,size位置是合法的,尾插index + 1 == size
System.err.println("add index illegal!");
return;
}
//插入全都是中间节点
Node node = new Node(val);
//遍历找到index位置的前驱节点
Node prev = dummyHead;
for(int i = 0;i < index;i++){
prev = prev.next;
}
//错误的写法：会报空指针异常
//eg:还未添加元素时,prev为null,此时,执行prev.next就会报错
// Node prev = dummyHead.next;
// for(int i = 0;i < index - 1;i++){
// prev = prev.next;
// }
//1)
node.next = prev.next;
//2):我的理解：(1)和(2)的步骤顺序不能交换
prev.next = node;
size++;
}
/**
*在第一个节点处添加节点
* @param val
*/
public void addFirst(int val){
addIndex(0,val);
}
/**
*在尾部添加节点
* @param val
*/
public void addLast(int val){
addIndex(size,val);
}
/**
* 删除方法
* @param index
*/
public void removeIndex(int index){
if(index < 0 || index > size){//此时,size是非法的,index + 1 = size
System.err.println("remove index illegal!");
return;
}
//定义一个辅助节点帮助遍历
//找到待删除节点的前驱节点
Node prev = dummyHead;
for(int i = 0;i < index;i++){
prev = prev.next;
}
prev = prev.next.next;//删除
size--;
}
public String toString(){
String ret = "";
Node node = dummyHead.next;
while(node != null){
ret += node.val;
ret += "->";
node = node.next;
}
ret += "NULL";
return ret;
}
}链表注意点
1）
A 链表题”=”可以看作指向符号(->)
prev.next = perv.next.next;
B.
temp = node;//表示将node节点的值赋给temp节点 2）超级重点：看你取值用的是那个引用,就判断那个引用不为空
或者这样理解：当前用的元素是谁,就要保证谁不为空
//超级重点：看你取值用的是那个引用,就判断那个引用不为空
while(prev.next != null){
if(prev.next.val == val){
prev.next = prev.next.next;//删除prev.next
size--;
return;
}
prev = prev.next;//后移,prev不是待删除节点的前驱
}三、详解单链表相关习题
不带头节点迭代
class Solution {
public ListNode removeElements(ListNode head, int val) {
//头节点就是待删除的节点
while(head != null && head.val == val){
head = head.next;
}
if(head == null){//删完之后，头节点有可能为空的情况
return head;
}else{//待删除节点一定在中间位置
ListNode prev = head;
while(prev.next != null){
if(prev.next.val == val){
ListNode cur = prev.next;
prev.next = cur.next;
}else{
//只有当prev.next.val != val
prev = prev.next;
}
}
}
return head;
}
}
带头结点迭代
class Solution {
public ListNode removeElements(ListNode head, int val) {
//虚拟头节点：取值必须在节点存储数据范围之外
ListNode dummyHead = new ListNode(-1);
//连接原来的链表
dummyHead.next = head;
ListNode prev = dummyHead;
while(prev.next != null){
if(prev.next.val == val){
prev.next = prev.next.next;
}else{
prev = prev.next;//后移
}
}
return dummyHead.next;
}
}递归
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
//将head.next以及之后节点交给removeElements解决
//head.next更新为删除后的子链表的头节点
head.next = removeElements(head.next,val);
if(head.val == val){
return head.next;
}
return head;
}
}子函数的作用：删除子链表中值为val的节点
带头节点迭代
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode prev = head;
while(prev.next != null){
if(prev.val == prev.next.val){
prev.next = prev.next.next;
}else{
prev = prev.next;
}
}
return head;
}
}不带头节点迭代
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummyHead = new ListNode(101);
dummyHead.next = head;
//有了虚拟头节点,prev指向第一个不重复元素
ListNode prev = dummyHead;
ListNode cur = dummyHead.next;
while(cur != null){
if(prev.val == cur.val){
//删除cur
prev.next = cur.next;
}else{
//pre和cur不是重复元素,都向后移动一个单位
prev = prev.next;
}
cur = cur.next;
}
return dummyHead.next;
}
}原地移动
class Solution {
public ListNode reverseList(ListNode head) {
//原地移动
if(head == null || head.next == null){
//只有一个节点或没有节点时,无需反转
return head;
}
ListNode prev = null;
ListNode cur = head;//当前需要处理的节点
while(cur != null){
//暂存一下处理节点的下一个节点
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}头插法
class Solution {
public ListNode reverseList(ListNode head) {
//头插法：会有额外的空间开辟(空间复杂度O(n))
if(head == null || head.next == null){
return head;
}
//新链表的虚拟头节点
ListNode dummyHead = new ListNode(5001);
while(head != null){
ListNode node = new ListNode(head.val);
//把当前节点插到原先链表的头
node.next = dummyHead.next;
//更新为当前最新的头节点
dummyHead.next = node;
head = head.next;
}
return dummyHead.next;
}
}
递归法
class Solution {
public ListNode reverseList(ListNode head) {
//递归
//递归出口
if(head == null || head.next == null){
return head;
}
ListNode sec = head.next;
//子函数的作用：反转第二个节点之后的子链表
ListNode newHead = reverseList(head.next);
//3.将sec.next = head;
//head.next = null;
sec.next = head;
head.next = null;
return newHead;
}
}子函数的作用：反转第二个节点之后的子链表
两次遍历
class Solution {
public ListNode middleNode(ListNode head) {
//暴力解法：遍历链表,获取链表size
//再次遍历：遍历到size / 2处
ListNode temp = head;
int size = 0;
while(temp != null){
size++;
temp = temp.next;
}
temp = head;
for(int i = 0;i < size / 2;i++){
temp = temp.next;
}
return temp;
}
}快慢指针法
class Solution {
public ListNode middleNode(ListNode head) {
//快慢指针法：
//快指针一次走两步,慢指针一次走一步,当快指针走完时,慢指针位于中间节点处
ListNode fast = head;
ListNode low = head;
//当fast为null(偶数节点) || fast.next == null(奇数个节点)
while(fast != null && fast.next != null){
fast = fast.next.next;
low = low.next;
}
return low;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/110919.html
