链表是一种用于存储数据集合的数据结构
属性：
1、 相邻的元素之间通过指针连接
2、 最后一个元素的后继指针值为null
3、 链表的长度是可变的
4、 链表的空间能够按需分配
链表通常是指单向链表，它包括多个结点，每个结点有一个后继元素的next指针。表中最后一个结点的next指针值为null，表示该链表的结束。
链表的基本操作主要有三个
1、 遍历链表；
2、 向链表中插入一个元素；
3、 从链表中删除一个元素；
下面是一个链表的类型声明：
public class ListNode {
/**
* 结点数据域
*/
private int data;
/**
* 结点的next指针
*/
private ListNode next;
/**
* 有参构造函数
* @param data 节点数据
*/
public ListNode(int data) {
this.data = data;
}
/**
* @return the data
*/
public int getData() {
return data;
}
/**
* @param data the data to set
*/
public void setData(int data) {
this.data = data;
}
/**
* @return the next
*/
public ListNode getNext() {
return next;
}
/**
* @param next the next to set
*/
public void setNext(ListNode next) {
this.next = next;
}
}
1、 求链表的长度；
/**
* 获取链表的长度
* @param headNode 头结点
* @return 链表的长度
*/
public static int getLength(ListNode headNode) {
int length = 0;
ListNode currentNode = headNode;
while (currentNode != null) {
length++;
currentNode = currentNode.getNext();
}
return length;
}
2、 遍历链表；
/**
* 遍历链表
* @param headNode 头结点
*/
public static void traverseLinkedList(ListNode headNode) {
ListNode currentNode = headNode;
while (currentNode != null) {
System.out.print(currentNode.getData() + " ");
currentNode = currentNode.getNext();
}
System.out.println();
}
3、 根据位置获取相应的结点；
/**
* 根据位置获取结点
* @param headNode 链表的头结点
* @param position 置位
* @return 位置结点
*/
public static ListNode getNodeByPosition(ListNode headNode, int position) {
// 检查需要查询的位置是否合法
int length = getLength(headNode);
if (position > length + 1 || position < 1) {
System.out.println("查询的位置不合法，有效的位置为：1 ~ " + (length + 1));
return null;
}
int count = 1;
ListNode currentNode = headNode;
while ((currentNode != null) && (count != position)) {
count++;
currentNode = currentNode.getNext();
}
return currentNode;
}
4、 根据位置插入结点；
/**
* 插入新结点
* @param headNode 头结点
* @param nodeToInsert 要插入的新结点
* @param position 要插入的位置
*/
public static ListNode insertLinkedListNode(ListNode headNode, ListNode nodeToInsert, int position) {
/*
* 判断链表是否存在
* 当链表不存在直接返回nodeToInsert作为链表的头结点
*/
if (headNode == null) {
return nodeToInsert;
}
/*
* 检查需要插入的位置是否合法
*/
int length = getLength(headNode);
if (position > length + 1 || position < 1) {
System.out.println("插入的位置不合法，有效的位置为：1 ~ " + (length + 1));
return headNode;
}
/*
* 插入新结点
* 1.向链表的开头插入新的结点
* 更新新结点的next指针，使其指向当前链表的表头
* 更新当前链表的表头指针的值，使其指向新结点
* 2.向单链表的尾部插入新结点
* 使新结点的next指针指向null
* 使当前链表的最后结点的next指针指向新结点
* 3.向单链表的中间插入新结点
* 先遍历找到位置结点的前驱结点
* 将前驱结点next指针指向的结点赋值给新结点的next指针
* 使前驱结点的next指针指向新结点
*/
if (position == 1) {
// 在单链表开头插入结点
nodeToInsert.setNext(headNode);
return nodeToInsert;
} else {
// 在链表中间或者尾部插入结点
int count = 1;
ListNode previousNode = headNode;
while(count < position - 1) {
previousNode = previousNode.getNext();
count++;
}
ListNode currentNode = previousNode.getNext();
nodeToInsert.setNext(currentNode);
previousNode.setNext(nodeToInsert);
}
return headNode;
}
5、 根据位置删除结点；
/**
* 根据位置删除结点
* @param headNode 头结点
* @param position 结点位置
* @return 删除位置结点后的链表
*/
public static ListNode deleteLinkedListNode(ListNode headNode, int position) {
/*
* 检查删除的位置是否合法
*/
int length = getLength(headNode);
if (position > length || position < 1) {
System.out.println("删除的位置不合法，有效的位置为：1 ~ " + (length + 1));
return headNode;
}
/*
* 单链表删除结点
* 1.删除单链表的头结点
* 创建一个临时结点指向表头指针指向的头节点
* 修改表头指针，使其指向下一个结点，并移除临时结点
* 2.删除单链表的最后一个结点
* 先遍历找到尾结点的前驱结点
* 使尾结点的next指针指向null
* 移除单链表的尾结点
* 3.删除单链表的中间结点
* 先遍历找到删除结点的前驱结点
* 使前驱结点的next指针指向删除结点next指针指向的值
* 移除单链表的删除结点
*/
if (position == 1) {
// 删除单链表的头结点
ListNode newHaedNode = headNode.getNext();
headNode = null;
return newHaedNode;
} else {
// 删除单链表的中间结点或者尾结点
int count = 1;
ListNode previousNode = headNode;
while(count < position - 1) {
previousNode = previousNode.getNext();
count++;
}
ListNode nodeToDelete = previousNode.getNext();
previousNode.setNext(nodeToDelete.getNext());
nodeToDelete = null;
}
return headNode;
}
单链表的基本操作先整理到这，下面将整理一些关于单链表的经典题目。
注：最近在复习数据结构，文章的内容主要根据《数据结构与算法经典问题分析》Java语言描述一书整理而来