链表是离散存储线性结构，物理地址上不要求连续。
- 链表优点
物理地址不需要连续，插入删除元素比较快 - 链表缺点
查询速度慢
现在用java来实现一个简单的链表，其中涉及到的算法有：添加，删除，查找，获取结点个数，查找倒数第k个结点，两个链表的公共结点。
-
链表结构
单向链表中主要由结点来体现的，而结点只包含两个域，数据域data+指向下一个结点的引用。
链表.png
如下所示：
/*********************************************************************结点定义*********************************************************/
//构成链表的结点（此处是单链表，每个结点都保存了指向下一个结点的引用）
class Node{
public int data;
public Node next;
public Node(int data,Node next){
this.data = data;
this.next = next;
}
}
而链表只需要知道头结点即可：
package com.wang.suan;
/**
* 链表
* @author wxe
* @since 0.0.1
*/
public class LinkedList {
private Node head;//头结点
/*********************************************************************结点定义*********************************************************/
//构成链表的结点（此处是单链表，每个结点都保存了指向下一个结点的引用）
class Node{
public int data;
public Node next;
public Node(int data,Node next){
this.data = data;
this.next = next;
}
}
}
链表中只定义了一个头结点，主要是为了方便其他比如遍历，插入等方法。
-
插入结点
- 插入到尾结点
这里我们先来介绍一下，插入到尾结点的算法。如果要插入到尾结点，那么势必需要先通过遍历链表获取到尾结点,时间复杂度为O(n)。比如我们要将value为data0数据插入到尾结点中：
图片.png
接下来我们先遍历找到尾结点，current当前指定的结点就是尾结点：
图片.png
执行插入时，新的结点就成了尾结点，其next指向null：
图片.png
执行插入操作，遍历到的尾结点的next执行新节点即可：
图片.png
算法如下：
/**
* 插入结点(插入到尾结点)
* @param value
* @return
*/
public void insertTail(int value){
Node current = head;
Node newNode = new Node(value, null);
if (head == null) {
//1.首次插入，为头结点
head = newNode;
} else {
//2.非首次插入,那么必须找到尾结点
while (current.next != null) {
current = current.next;
}
current.next = newNode;//将新节点添加到尾结点
}
}
- 插入到头结点
有时候链表为了节省时间，就插在头结点处。由于不用遍历整个链表寻找尾结点，所以时间复杂度为O(n)，比如我们要将value为data0数据插入到头结点中。
图片.png
执行插入操作，分两步如下所示：
图片.png
图片.png
整理一下就是：
图片.png
算法如下：
/**
* 插入头结点，时间复杂度为O(1)
* @param value
*/
public void insertHead(int value){
Node newNode = new Node(value, null);
if (head != null) {
newNode.next = head.next;
}
head = newNode;
}
-
插入指定位置
插入指定位置，那么我们首先要找到这个位置上的结点，然后再执行插入操作，比如将data0数据项插入到index为2的位置：
图片.png
先找到index=2位置处的结点：
图片.png
然后执行插入操作：
图片.png
图片.png
整理一下就是：
图片.png
实现代码如下：
/**
* 指定位置添加结点,先遍历链表找到index-1位置上的结点和index上的结点
* @param value
* @param index
*/
public void add(int value,int index){
Node newNode = new Node(value, null);
//1.检验插入位置是否合法
if (index <1 || index > size()) {
System.out.println("输入位置不合法！");
return;
}
Node current = head;
int currentPos = 0;
while(current.next != null){
currentPos ++;
if (index == currentPos ) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}
}
-
删除结点
- 时间复杂度为O(n)
删除结点，我们首先要知道删除的那个结点位置，还要知道删除结点的前一个结点和后一个结点。然后直接将要删除结点的前一个结点的next指向后一个结点即可。但是我们不需要注意到这个结点是否为空，是否为头结点，是否为尾结点等边界条件，由于需要遍历需要这个结点，因此其时间复杂度为O(n).比如我们要删除数据项为data2的结点。
图片.png
首先我们要找到删除的结点delNode和前一个结点preNode:
图片.png
然后直接将preNode的next指向delNode的next，然后清空delNode就可以了。
图片.png
实现代码如下：
/**
* 删除指定结点，首先要找到删除的结点的位置,还必须找到该节点的前置，后置结点。O(n)时间复杂度
* @param value
* @return
*/
public void delete(int value){
Node current = head;
Node preNode = head;
Node delNode = null;
while (current.next != null) {
if (current.data == value) {
delNode = current;
break;
}
preNode = current;
current = current.next;
}
if (delNode == null) {
return ;
}
if (delNode == head) {
//如果删除的是头结点
head = delNode.next;
} else if (delNode.next == null) {
//如果删除的是尾结点
preNode.next = null;
} else {
preNode.next = delNode.next;
}
delNode = null;
}
-
时间复杂度为O(1)
剑指offer中有一道关于删除链表的算法题，给定头结点，和一个结点指针，要求时间复杂度为O(1)时间删除该结点。首先我们需要明白给定的这个结点指针，不仅有值，而且还有指向下一个结点的引用。那么就是说，如果我们将下一个结点的值复制到该结点中，再将下一个结点的next指向复制给该节点的next。好像就实现了删除这个结点的操作。但是这是建立在这个结点必须存在于链表中，而且该节点不能为尾结点，因为如果为尾结点的话，还是需要遍历整个链表的。这样一来时间复杂度为 O(n)。我们计算一下平均复杂度为：[（n-1）*O(n) + O(n) ] / n ，时间复杂度其实还是O(1)是符合要求的。比如要删除delNode = new Node(data2,nextNode)：
图片.png
首先将nextNode中的数据项复制到要删除的node中
图片.png
然后再将该结点的next指向nextNode的next，如图所示：
图片.png
如果正好只有一个结点的话，head结点直接为null了。
或者删除的是尾结点，那么必须遍历了，参考上面O(n)算法删除操作。
实现代码如下：
/**
* 删除结点(O(1)时间复杂度)，可以用被删除结点的下一个结点P1覆盖被删除的结点P2，然后再删除P1结点即可。
* @param value
*/
public void deleteNode(Node delNode){
if (head == null) {
return;
}
//如果删除的不是尾结点
if (delNode.next != null) {
//1.找到下一个结点
Node nextNode = delNode.next;
//2.复制下一个结点给要删除的结点
delNode.data = nextNode.data;
delNode.next = nextNode.next;
nextNode = null;//方便回收
}
//如果正好只有一个结点，头结点就是尾结点
else if (head == delNode) {
head = null;
delNode = null;
}
//链表中有多个结点，删除尾结点
else {
Node current = head;
while (current.next != delNode) {
current = current.next;
}
current.next = null;
delNode = null;
}
}
-
查找倒数第k个结点
要查找倒数第k个结点，假设链表有n个结点，那么第K个结点就是从前到后遍历到的第n-k+1个结点。这个时候我们有一种思路就是遍历一遍链表知道这个链表的结点数n，然后再遍历一遍链表找到第n-k+1结点，就是所谓的第K个结点。但是这样一来，相当于我们遍历了两次链表。我们还可以使用一些技巧只遍历一次链表就可以了。我们可以定义两个指针，一个指针preKNode先向前走k-1个位置，然后另一个指针current和preKNode同时遍历链表，直到preKNode遍历到尾结点，那么current指向的就是倒数第k个结点。比如我们要找到倒数第2个结点，也就是数据项为data2的结点。分析如下：
图片.png
现在先让preKNode向前走k-1步，也就是1步：
图片.png
然后两个指针同时向前走，直到preKNode到达尾结点：
图片.png
图片.png
那么current指针指向的就是倒数第K个结点了。
实现代码如下：
/**
* 查找倒数第k个结点
* @param value
* @param k
* @return
*/
public Node findKNode(int k){
Node current = head;
Node preKNode = head;
//preKNode为第k-1个结点
for (int i = 0; i < k-1; i++) {
preKNode = preKNode.next;
}
//当第k-1的结点遍历到了尾结点，current就是第k个结点
while (preKNode.next != null) {
preKNode = preKNode.next;
current = current.next;
}
return current;
}
-
反转链表
比如我们通过遍历链表的方式来反转如下链表：
图片.png
首先，我们定义两个指针，分别指向相邻的两个结点一个是current，一个是preNode，我们只需要将current的next指向上一个结点preNode，就相当于做了一次反转，可是我们知道current.next指向preNode时，相当于data1和data2两个结点断了关系，没有办法继续遍历下去了。此时，我们在断开data1和data2之前就需要一个临时结点保存tempNode来保存data1的next,也就是tempNode = current.next;这样才能继续保持遍历链表。
第一次反转，头结点相当于尾结点了。
第一次反转.png
继续向下遍历
图片.png
继续向下遍历
图片.png
继续向下走：
图片.png
此时反转完成，而preNode成为了新的头结点，直接返回即可。
实现代码如下：
/**
* 反转链表，并返回头结点
*
* @return
*/
public Node reverse() {
//空链表
if (head == null) {
return head;
}
//只有一个结点
if (head.next == null) {
return head;
}
Node preNode = head;// 上一结点
Node current = head.next;// 当前结点
Node tempNode = null;
while (current != null) {
tempNode = current.next;
if (preNode == head) {
preNode.next = null;
}
current.next = preNode;//指针方向反转
preNode = current;//preNode向前移动
current = tempNode;//current向前移动
}
return preNode;
}
-
合并两个排序的链表
比如对这两个链表进行排序
图片.png
其实，这里就是通过遍历两个链表，通过比较两个链表的结点然后找到合适的合并后的结点。如下所示：
图片.png
我们来进行第一次比较，也就是找到第一个合适的合并后的结点mergeNode。由于p1.data < p2.data，因此，此时mergeNode应该指向p1，如下所示：
图片.png
找到了头结点，我们来找一下mergeNode的下一个结点，开始第二次比较：
图片.png
继续比较，寻找mergeNode的下一个结点，开始第三次比较：
图片.png
依次类推下去，我们知道每次找到了mergeNode其实我们都用了相同的比较方法来寻找其下一个结点，这种就可以用递归的方法来表达了。知道最后完成比较并排序，结果如下所示：
图片.png
实现代码如下：
/**
* 用递归方式合并两个有序链表，并保持合并后的链表有序
* @param head1
* @param head2
* @return
*/
public Node mergeList(Node head1,Node head2){
Node mergedNode = null; //合并后的结点
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.data < head2.data) {
mergedNode = head1;
mergedNode.next = mergeList(head1.next, head2);
} else {
mergedNode = head2;
mergedNode.next = mergeList(head1, head2.next);
}
return mergedNode;
}
-
两个链表的第一个公共结点
题目是：输入两个链表，找到他们的第一个公共结点。
先来理解一下这个题目哈，找到第一个公共节点，那说明这个公共结点之后的结点都是一样的。所以，从第一个公共节点开始之后的结点都是重合的。看起来像了一个Y字。比如，下面两个链表：
图片.png
那么其实这个时候，我们肯定不能通过遍历一个链表（m个结点），然后再另个一个链表（n个结点）中找到相同数据项的结点，这样子的算法相当于是O(mn)的时间效率。
可以这么考虑，如果我们保持两个链表长度相同，同时遍历链表然后进行比较。这样提高了时间效率。但是给出的链表长度是未知的，不一定是相同的，这个时候，我们需要以长度短的链表为主来寻找第一个公共结点。也就是说，链表比较长的，我们先要走一定的步数，让其保持和另一个链表长度一致，然后再同时遍历比较。
实现代码如下：
/**
* 查找第一个公共祖先
* @param head1
* @param head2
* @return
*/
public Node findFirstCommonNode(Node head1,Node head2){
if (head1 == null || head2 == null) {
return null;
}
int size1 = size(head1);
int size2 = size(head2);
int diff = size1 - size2;
Node longNode = head1;
Node shortNode = head2;
if (diff < 0) {
diff = size2 - size1;
longNode = head2;
shortNode = head1;
}
//让长的链表先走diff步
for (int i = 0; i < diff; i++) {
longNode = longNode.next;
}
//现在长度一致同时遍历
while (longNode != null && shortNode != null && longNode.data != shortNode.data) {
longNode = longNode.next;
shortNode = shortNode.next;
}
return longNode;
}
public int size(Node head) {
int size = 0;
if (head == null) {
return size;
}
while (head.next != null) {
head = head.next;
size++;
}
return size + 1;// 加上最后一个尾结点个数
}
-
寻找中间结点
设置一个快慢指针，快指针P2每次走两步，慢指针P1每次走一步，由于快指针P2走的快，因此要注意结束条件以P2为主。比如我们要寻找下面这个链表的中间结点：
图片.png
P1走一步，P2走两步，如下所示：
图片.png
由上面我们可以看到P2只能走一步，没有办法再走两步了，因此这里已经达到结束时间了。P1指向的就是中间结点。
或者我们看看链表长度为奇数时：
图片.png
P1走一步，P2走两步，如下所示：
图片.png
P2此时没法走两步，达到结束条件。P1指向的就是中间结点。
代码实现如下：
/**
* 查找中间结点
* @return
*/
public Node findMiddleNode(Node head){
Node p1 = head;
Node p2 = head;
if (head == null) {
//空链表
return null;
} else if (head.next == null) {
//只有一个结点
return head;
} else {
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
}
return p1;
}
最后附上所有的源代码
package com.wang.suan;
/**
* 链表
*
* @author wxe
* @since 0.0.1
*/
public class LinkedList {
private Node head;// 头结点
/******************************************************* 链表的增删改查操作 *********************************************************************/
/**
* 插入结点(插入到尾结点)
*
* @param value
* @return
*/
public void insertTail(int value) {
Node current = head;
Node newNode = new Node(value, null);
if (head == null) {
// 1.首次插入，为头结点
head = newNode;
} else {
// 2.非首次插入,那么必须找到尾结点
while (current.next != null) {
current = current.next;
}
current.next = newNode;// 将新节点添加到尾结点
}
}
/**
* 插入头结点，时间复杂度为O(1)
*
* @param value
*/
public void insertHead(int value) {
Node newNode = new Node(value, null);
if (head != null) {
newNode.next = head.next;
}
head = newNode;
}
/**
* 查找结点
*
* @param value
* @return
*/
public Node find(int value) {
Node current = head;
while (current.next != null) {
if (current.data == value) {
return current;
}
current = current.next;
}
return null;
}
/**
* 删除指定结点，首先要找到删除的结点的位置,还必须找到该节点的前置，后置结点。O(n)时间复杂度
*
* @param value
* @return
*/
public void delete(int value) {
Node current = head;
Node preNode = head;
Node delNode = null;
while (current.next != null) {
if (current.data == value) {
delNode = current;
break;
}
preNode = current;
current = current.next;
}
if (delNode == null) {
return;
}
if (delNode == head) {
// 如果删除的是头结点
head = delNode.next;
} else if (delNode.next == null) {
// 如果删除的是尾结点
preNode.next = null;
} else {
preNode.next = delNode.next;
}
delNode = null;
}
/**
* 删除结点(O(1)时间复杂度)，可以用被删除结点的下一个结点P1覆盖被删除的结点P2，然后再删除P1结点即可。
*
* @param value
*/
public void deleteNode(Node delNode) {
if (head == null) {
return;
}
// 如果删除的不是尾结点
if (delNode.next != null) {
// 1.找到下一个结点
Node nextNode = delNode.next;
// 2.复制下一个结点给要删除的结点
delNode.data = nextNode.data;
delNode.next = nextNode.next;
nextNode = null;// 方便回收
}
// 如果正好只有一个
else if (head == delNode) {
head = null;
delNode = null;
}
// 链表中有多个结点，删除尾结点
else {
Node current = head;
while (current.next != delNode) {
current = current.next;
}
current.next = null;
delNode = null;
}
}
/**
* 指定位置添加结点,先遍历链表找到index-1位置上的结点和index上的结点
*
* @param value
* @param index
*/
public void add(int value, int index) {
Node newNode = new Node(value, null);
// 1.检验插入位置是否合法
if (index < 1 || index > size()) {
System.out.println("输入位置不合法！");
return;
}
Node current = head;
int currentPos = 0;
while (current.next != null) {
currentPos++;
if (index == currentPos) {
newNode.next = current.next;
current.next = newNode;
return;
}
current = current.next;
}
}
/**
* 获取结点个数
*
* @return
*/
public int size() {
int size = 0;
if (head == null) {
return 0;
}
Node current = head;
while (current.next != null) {
current = current.next;
size++;
}
return size + 1;// 加上最后一个尾结点个数
}
public int size(Node head) {
int size = 0;
if (head == null) {
return size;
}
while (head.next != null) {
head = head.next;
size++;
}
return size + 1;// 加上最后一个尾结点个数
}
/**
* 查找倒数第k个结点
*
* @param value
* @param k
* @return
*/
public Node findKNode(int k) {
Node current = head;
Node preKNode = head;
// preKNode为第k-1个结点
for (int i = 0; i < k - 1; i++) {
preKNode = preKNode.next;
}
// 当第k-1的结点遍历到了尾结点，current就是第k个结点
while (preKNode.next != null) {
preKNode = preKNode.next;
current = current.next;
}
return current;
}
/**
* 反转链表，并返回头结点
*
* @return
*/
public Node reverse() {
//空链表
if (head == null) {
return head;
}
//只有一个结点
if (head.next == null) {
return head;
}
Node preNode = head;// 上一结点
Node current = head.next;// 当前结点
Node tempNode = null;
while (current != null) {
tempNode = current.next;
if (preNode == head) {
preNode.next = null;
}
current.next = preNode;//指针方向反转
preNode = current;//preNode向前移动
current = tempNode;//current向前移动
}
return preNode;
}
/**
* 用递归方式合并两个有序链表，并保持合并后的链表有序
* @param head1
* @param head2
* @return
*/
public Node mergeList(Node head1,Node head2){
Node mergedNode = null; //合并后的结点
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
if (head1.data < head2.data) {
mergedNode = head1;
mergedNode.next = mergeList(head1.next, head2);
} else {
mergedNode = head2;
mergedNode.next = mergeList(head1, head2.next);
}
System.out.println(mergedNode.data);
return mergedNode;
}
/**
* 查找第一个公共祖先
* @param head1
* @param head2
* @return
*/
public Node findFirstCommonNode(Node head1,Node head2){
if (head1 == null || head2 == null) {
return null;
}
int size1 = size(head1);
int size2 = size(head2);
int diff = size1 - size2;
Node longNode = head1;
Node shortNode = head2;
if (diff < 0) {
diff = size2 - size1;
longNode = head2;
shortNode = head1;
}
//让长的链表先走diff步
for (int i = 0; i < diff; i++) {
longNode = longNode.next;
}
//现在长度一致同时遍历
while (longNode != null && shortNode != null && longNode.data != shortNode.data) {
longNode = longNode.next;
shortNode = shortNode.next;
}
return longNode;
}
/**
* 查找中间结点
* @return
*/
public Node findMiddleNode(Node head){
Node p1 = head;
Node p2 = head;
if (head == null) {
//空链表
return null;
} else if (head.next == null) {
//只有一个结点
return head;
} else {
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
}
return p1;
}
public void display() {
if (head != null) {
while (head.next != null) {
System.out.println(head.data);
}
}
}
/********************************************************************* 结点定义 *********************************************************/
// 构成链表的结点（此处是单链表，每个结点都保存了指向下一个结点的引用）
class Node {
public int data;
public Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
/**************************************************** *********测试链表 ******************************************************************/
public static void main(String[] args) {
// LinkedList list = new LinkedList();
// list.insertTail(1);
// list.insertTail(2);
// list.insertTail(3);
// list.insertTail(4);
//
//
//
// System.out.println(list.head.data);
// // System.out.println(list.find(6));
// // System.out.println(list.size());
// System.out.println(list.findKNode(2).data);
//// list.reverse();
// System.out.println(list.reverse().data);
// System.out.println(list.findKNode(2).data);
LinkedList list = new LinkedList();
list.insertTail(1);
list.insertTail(2);
list.insertTail(5);
list.insertTail(7);
list.insertTail(9);
LinkedList list2= new LinkedList();
list2.insertTail(2);
list2.insertTail(4);
list2.insertTail(8);
// System.out.println(list.mergeList(list.head, list2.head).data);
// System.out.println(list.findFirstCommonNode(list.head, list2.head).data);
System.out.println(list.findMiddleNode(list.head).data);
}
}
