链表（Java）

链表常见的操作：

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