鏈表常見(jiàn)的操作：

1、插入節(jié)點(diǎn)（頭插、尾插）
2、刪除節(jié)點(diǎn)
3、獲取鏈表長(zhǎng)度
4、逆序打印
5、反轉(zhuǎn)鏈表
6、判斷鏈表是否有環(huán)
7、判斷鏈表是否相交
8、如果相交，返回第一個(gè)開(kāi)始相交的節(jié)點(diǎn)
9、查找單鏈表中第K個(gè)節(jié)點(diǎn)
10、尋找單鏈表的中間結(jié)點(diǎn)

代碼外加注釋如下

class LinkList{
    Node header;
    static class Node{
        int data;
        Node next;
        public Node(int data){
            this.data = data;
        }
    }
    
    /*
     * 頭插法
     * 被插入node的next指向header，則成為第一個(gè)
     * 將header移動(dòng)到頭部
     */
    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;
        }
    }
/**
     * 鏈表刪除結(jié)點(diǎn):
     * 把要?jiǎng)h除結(jié)點(diǎn)的前結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后結(jié)點(diǎn)，即直接跳過(guò)待刪除結(jié)點(diǎn)
     * @param index
     * @return
     */
    public boolean deleteNode(int index){
        if(index<1 || index>getLength(header)){//待刪除結(jié)點(diǎn)不存在
            return false;
        }
        if(index == 1){//刪除頭結(jié)點(diǎn)
            header = header.next;
            return true;
        }
        Node preNode = header;
        Node curNode = preNode.next;
        int i = 1;
        while(curNode != null){
            if(i==index){//尋找到待刪除結(jié)點(diǎn)
                preNode.next = curNode.next;//待刪除結(jié)點(diǎn)的前結(jié)點(diǎn)指向待刪除結(jié)點(diǎn)的后結(jié)點(diǎn)
                return true;
            }
            //當(dāng)先結(jié)點(diǎn)和前結(jié)點(diǎn)同時(shí)向后移
            preNode = preNode.next;
            curNode = curNode.next;
            i++;
        }
        return true;
    }
    
    /**
     * 長(zhǎng)度
     * @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;
        }
    }
    
    /**
     * 反轉(zhuǎn)鏈表
     */
    public void reverseLink(){
        Node curNode = header;
        Node preNode = null;
        Node nextNode = null;
        while(curNode!=null){
            nextNode = curNode.next;//保留下一個(gè)節(jié)點(diǎn)（因?yàn)橐獢嚅_(kāi)下面了）
            curNode.next = preNode;//反轉(zhuǎn)指針到前面
            //移動(dòng)節(jié)點(diǎn)為了繼續(xù)下一次保存、斷開(kāi)、反轉(zhuǎn)
            preNode = curNode;
            curNode = nextNode;
        }
        header = preNode;
    }
    
    /**
     * 創(chuàng)建有環(huán)鏈表只為測(cè)試用
     */
    public void createRing(){
        header = new Node(1);
        header.next = header;
    }
    
    /**
     * 是否有環(huán)
     * 設(shè)置快指針和慢指針，慢指針每次走一步，快指針每次走兩步
     * 當(dāng)快指針與慢指針相等時(shí)，就說(shuō)明該鏈表有環(huán)
     */
    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;
    }
    
    /**
     * 創(chuàng)建添加節(jié)點(diǎn)的鏈表方法，為測(cè)試相交
     */
    public void add(Node node){
        if(node==null){
            return;
        }
        if(header==null){
            header = node;
        }else{
            node.next = header;
            header = node;
        }
    }
    
    /**
     * 兩個(gè)鏈表是否相交
     * 兩個(gè)鏈表相交，則它們的尾結(jié)點(diǎn)一定相同，比較兩個(gè)鏈表的尾結(jié)點(diǎn)是否相同即可
     */
    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;
    }
    
     /**
     * 如果鏈表相交，求鏈表相交的起始點(diǎn)：
     * 1、首先判斷鏈表是否相交，如果兩個(gè)鏈表不相交，則求相交起點(diǎn)沒(méi)有意義
     * 2、求出兩個(gè)鏈表長(zhǎng)度之差：len=length1-length2
     * 3、讓較長(zhǎng)的鏈表先走len步
     * 4、然后兩個(gè)鏈表同步向前移動(dòng)，沒(méi)移動(dòng)一次就比較它們的結(jié)點(diǎn)是否相等，第一個(gè)相等的結(jié)點(diǎn)即為它們的第一個(gè)相交點(diǎn)
     */
    public static Node findFirstCrossPoint(LinkList linkedList1, LinkList linkedList2){
        //鏈表不相交
        if(!isCross(linkedList1.header,linkedList2.header)){
            return null;
        }else{
            int length1 = linkedList1.getLength(linkedList1.header);//鏈表1的長(zhǎng)度
            int length2 = linkedList2.getLength(linkedList2.header);//鏈表2的長(zhǎng)度
            Node temp1 = linkedList1.header;//鏈表1的頭結(jié)點(diǎn)
            Node temp2 = linkedList2.header;//鏈表2的頭結(jié)點(diǎn)
            int len = length1 - length2;//鏈表1和鏈表2的長(zhǎng)度差
            
            if(len > 0){//鏈表1比鏈表2長(zhǎng)，鏈表1先前移len步        
                for(int i=0; i<len; i++){
                    temp1 = temp1.next;
                }
            }else{//鏈表2比鏈表1長(zhǎng)，鏈表2先前移len步
                for(int i=0; i<-len; i++){
                    temp2 = temp2.next;
                }
            }
            //鏈表1和鏈表2同時(shí)前移,直到找到鏈表1和鏈表2相交的結(jié)點(diǎn)
            while(temp1 != temp2){
                temp1 = temp1.next;
                temp2 = temp2.next;
            }
            return temp1;
        }
    }
    
    /**
     * 查找單鏈表中第K個(gè)節(jié)點(diǎn)
     * 第二種解法是快慢指針,主要思路就是使用兩個(gè)指針，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)，
     * 后面的指針才走，這樣前后兩個(gè)指針的距離差是k-1，之后前后兩個(gè)指針一起向前走，
     * 前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)
     */
    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;
    }
    
    /**
     * 尋找單鏈表的中間結(jié)點(diǎn)：
     * 方法一、先求出鏈表的長(zhǎng)度，再遍歷1/2鏈表長(zhǎng)度，尋找出鏈表的中間結(jié)點(diǎn)
     * 方法二、：
     * 用兩個(gè)指針遍歷鏈表，一個(gè)快指針、一個(gè)慢指針，
     * 快指針每次向前移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針一次向前移動(dòng)一個(gè)結(jié)點(diǎn)，
     * 當(dāng)快指針移動(dòng)到鏈表的末尾，慢指針?biāo)诘奈恢眉礊橹虚g結(jié)點(diǎn)所在的位置 
     */
    public Node findMiddleNode(){
        Node slowPoint = header;
        Node quickPoint = header;
        //鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前一個(gè)
        while(quickPoint.next != null && quickPoint.next.next != null){
            slowPoint = slowPoint.next;
            quickPoint = quickPoint.next.next;
        }
        return slowPoint;
    }

}

測(cè)試代碼如下：

public class LinkTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //測(cè)試尾插法和遞歸從尾達(dá)到頭打印
        System.out.println("---------測(cè)試尾插法和遞歸打印----------");
        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();
        //測(cè)試頭插法和棧從尾達(dá)到頭打印
        System.out.println("---------測(cè)試頭插法和棧打印----------");
        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();
        //測(cè)試反轉(zhuǎn)
        System.out.println("---------測(cè)試反轉(zhuǎn)----------");
        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();
        //測(cè)試有環(huán)
        System.out.println("---------測(cè)試有環(huán)----------");
        LinkList mLink3 = new LinkList();
        mLink3.createRing();
        System.out.println("是否有環(huán)："+mLink3.isRing());
        System.out.println("---------測(cè)試相交----------");
        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("相交的起始節(jié)點(diǎn)："+LinkList.findFirstCrossPoint(mLink4, mLink5).data);
        System.out.println("---------測(cè)試返回倒數(shù)第k個(gè)節(jié)點(diǎn)----------");
        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);
    }

}

打印如下：

---------測(cè)試尾插法和遞歸打印----------
3
3 2 1 
---------測(cè)試頭插法和棧打印----------
4
1 2 3 4 

---------測(cè)試反轉(zhuǎn)----------
8 7 6 5 
---------測(cè)試有環(huán)----------
是否有環(huán)：true
---------測(cè)試相交----------
是否相交：true
相交的起始節(jié)點(diǎn)：0
---------測(cè)試尾插法和遞歸打印----------
5

相關(guān)博文：
java實(shí)現(xiàn)單鏈表常見(jiàn)操作 ----方法思路標(biāo)注詳細(xì)
面試中的Java鏈表---這個(gè)是一個(gè)面試題一個(gè)解
http://www.itdecent.cn/p/6ebedde370b0