链表常见的操作：
1、插入节点（头插、尾插）
2、删除节点
3、获取链表长度
4、逆序打印
5、反转链表
6、判断链表是否有环
7、判断链表是否相交
8、如果相交，返回第一个开始相交的节点
9、查找单链表中第K个节点
10、寻找单链表的中间结点
代码外加注释如下
class LinkList{
Node header;
static class Node{
int data;
Node next;
public Node(int data){
this.data = data;
}
}
/*
* 头插法
* 被插入node的next指向header，则成为第一个
* 将header移动到头部
*/
public void addNodeHead(int data){
Node newNode = new Node(data);
if(header==null){
header = newNode;
}else{
newNode.next = header;
header = newNode;
}
}
/**
* 尾插法
*/
public void addNodeEnd(int data){
Node newNode = new Node(data);
if(header==null){
header = newNode;
}else{
Node temp = header;
while(temp.next!=null){
temp = temp.next;
}
temp.next = newNode;
}
}
/**
* 链表删除结点:
* 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
* @param index
* @return
*/
public boolean deleteNode(int index){
if(index<1 || index>getLength(header)){//待删除结点不存在
return false;
}
if(index == 1){//删除头结点
header = header.next;
return true;
}
Node preNode = header;
Node curNode = preNode.next;
int i = 1;
while(curNode != null){
if(i==index){//寻找到待删除结点
preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
return true;
}
//当先结点和前结点同时向后移
preNode = preNode.next;
curNode = curNode.next;
i++;
}
return true;
}
/**
* 长度
* @param header
* @return
*/
public int getLength(Node header){
int num = 0;
while(header!=null){
num++;
header = header.next;
}
return num;
}
/**
* 从尾到头打印链表
* 建栈
*/
public void reversePrintLink(Node node){
Stack<Node> stack = new Stack<Node>();
while(node!=null){
stack.push(node);
node = node.next;
}
while(!stack.isEmpty()){
System.out.print(stack.pop().data+" ");
}
System.out.println();
}
/**
* 从尾到头打印链表
* 递归
*/
public void reversePrintLink1(Node node){
if(node!=null){
reversePrintLink1(node.next);
System.out.print(node.data+" ");
}
}
/**
* 正序打印
*/
public void printLink(Node node){
while(node!=null){
System.out.print(node.data+" ");
node = node.next;
}
}
/**
* 反转链表
*/
public void reverseLink(){
Node curNode = header;
Node preNode = null;
Node nextNode = null;
while(curNode!=null){
nextNode = curNode.next;//保留下一个节点（因为要断开下面了）
curNode.next = preNode;//反转指针到前面
//移动节点为了继续下一次保存、断开、反转
preNode = curNode;
curNode = nextNode;
}
header = preNode;
}
/**
* 创建有环链表只为测试用
*/
public void createRing(){
header = new Node(1);
header.next = header;
}
/**
* 是否有环
* 设置快指针和慢指针，慢指针每次走一步，快指针每次走两步
* 当快指针与慢指针相等时，就说明该链表有环
*/
public boolean isRing(){
if(header == null){
return false;
}
Node slow = header;
Node fast = header;
if(fast.next!=null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
/**
* 创建添加节点的链表方法，为测试相交
*/
public void add(Node node){
if(node==null){
return;
}
if(header==null){
header = node;
}else{
node.next = header;
header = node;
}
}
/**
* 两个链表是否相交
* 两个链表相交，则它们的尾结点一定相同，比较两个链表的尾结点是否相同即可
*/
public static boolean isCross(Node head1,Node head2){
if(head1==null||head2==null){
return false;
}
Node temp1 = head1;
Node temp2 = head2;
while(temp1.next!=null){
temp1 = temp1.next;
}
while(temp2.next!=null){
temp2 = temp2.next;
}
return temp1 == temp2;
}
/**
* 如果链表相交，求链表相交的起始点：
* 1、首先判断链表是否相交，如果两个链表不相交，则求相交起点没有意义
* 2、求出两个链表长度之差：len=length1-length2
* 3、让较长的链表先走len步
* 4、然后两个链表同步向前移动，没移动一次就比较它们的结点是否相等，第一个相等的结点即为它们的第一个相交点
*/
public static Node findFirstCrossPoint(LinkList linkedList1, LinkList linkedList2){
//链表不相交
if(!isCross(linkedList1.header,linkedList2.header)){
return null;
}else{
int length1 = linkedList1.getLength(linkedList1.header);//链表1的长度
int length2 = linkedList2.getLength(linkedList2.header);//链表2的长度
Node temp1 = linkedList1.header;//链表1的头结点
Node temp2 = linkedList2.header;//链表2的头结点
int len = length1 - length2;//链表1和链表2的长度差
if(len > 0){//链表1比链表2长，链表1先前移len步
for(int i=0; i<len; i++){
temp1 = temp1.next;
}
}else{//链表2比链表1长，链表2先前移len步
for(int i=0; i<-len; i++){
temp2 = temp2.next;
}
}
//链表1和链表2同时前移,直到找到链表1和链表2相交的结点
while(temp1 != temp2){
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
}
/**
* 查找单链表中第K个节点
* 第二种解法是快慢指针,主要思路就是使用两个指针，先让前面的指针走到正向第k个结点，
* 后面的指针才走，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，
* 前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点
*/
public Node getKNode(Node head,int k){
if(k<0||k>getLength(header)){
return null;
}
Node first = head;
Node last = head;
for(int i=1;i<k;i++){
first = first.next;
}
while(first.next!=null){
first = first.next;
last = last.next;
}
return last;
}
/**
* 寻找单链表的中间结点：
* 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
* 方法二、：
* 用两个指针遍历链表，一个快指针、一个慢指针，
* 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
* 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
*/
public Node findMiddleNode(){
Node slowPoint = header;
Node quickPoint = header;
//链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
while(quickPoint.next != null && quickPoint.next.next != null){
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint;
}
}
测试代码如下：
public class LinkTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//测试尾插法和递归从尾达到头打印
System.out.println("---------测试尾插法和递归打印----------");
LinkList mLink = new LinkList();
mLink.addNodeEnd(1);
mLink.addNodeEnd(2);
mLink.addNodeEnd(3);
System.out.println(mLink.getLength(mLink.header));
mLink.reversePrintLink1(mLink.header);
System.out.println();
//测试头插法和栈从尾达到头打印
System.out.println("---------测试头插法和栈打印----------");
LinkList mLink1 = new LinkList();
mLink1.addNodeHead(1);
mLink1.addNodeHead(2);
mLink1.addNodeHead(3);
mLink1.addNodeHead(4);
System.out.println(mLink1.getLength(mLink1.header));
mLink1.reversePrintLink(mLink1.header);
System.out.println();
//测试反转
System.out.println("---------测试反转----------");
LinkList mLink2 = new LinkList();
mLink2.addNodeEnd(5);
mLink2.addNodeEnd(6);
mLink2.addNodeEnd(7);
mLink2.addNodeEnd(8);
mLink2.reverseLink();
mLink2.printLink(mLink2.header);
System.out.println();
//测试有环
System.out.println("---------测试有环----------");
LinkList mLink3 = new LinkList();
mLink3.createRing();
System.out.println("是否有环："+mLink3.isRing());
System.out.println("---------测试相交----------");
LinkList mLink4 = new LinkList();
LinkList mLink5 = new LinkList();
LinkList.Node node = new LinkList.Node(0);
mLink4.addNodeHead(1);
mLink5.addNodeHead(1);
mLink4.add(node);
mLink5.add(node);
mLink5.addNodeHead(2);
System.out.println("是否相交："+LinkList.isCross(mLink4.header,mLink5.header));
System.out.println("相交的起始节点："+LinkList.findFirstCrossPoint(mLink4, mLink5).data);
System.out.println("---------测试返回倒数第k个节点----------");
LinkList mLink6 = new LinkList();
mLink6.addNodeEnd(1);
mLink6.addNodeEnd(2);
mLink6.addNodeEnd(3);
mLink6.addNodeEnd(4);
mLink6.addNodeEnd(5);
mLink6.addNodeEnd(6);
System.out.println(mLink6.getKNode(mLink6.header, 2).data);
}
}
打印如下：
---------测试尾插法和递归打印----------
3
3 2 1
---------测试头插法和栈打印----------
4
1 2 3 4
---------测试反转----------
8 7 6 5
---------测试有环----------
是否有环：true
---------测试相交----------
是否相交：true
相交的起始节点：0
---------测试尾插法和递归打印----------
5
相关博文：
java实现单链表常见操作 ----方法思路标注详细
面试中的Java链表---这个是一个面试题一个解
https://www.jianshu.com/p/6ebedde370b0
