??由于涉及到Floyd判環(huán)算法，故先簡單闡述一下Floyd判環(huán)算法原理。

Floyd判環(huán)算法

算法原理：設(shè)置兩個指針同時(shí)從頭結(jié)點(diǎn)向后訪問（當(dāng)兩指針后繼不為null），不過兩指針的訪問速度不一致，第一個指針每次后移一個元素，第二個指針每次后移兩個元素。若鏈表成環(huán)，則兩指針在某一時(shí)刻必然相遇，否則不相遇

計(jì)算環(huán)長度：
當(dāng)指針相遇時(shí)，保持其中一個指針不動，另一個指針向后訪問，每次后移一個單位，當(dāng)兩指針再次相遇時(shí)，該指針移動的單位即為環(huán)的長度

計(jì)算環(huán)起始節(jié)點(diǎn)：
第一次相遇后，慢指針從頭結(jié)點(diǎn)向后訪問，快指針從相遇點(diǎn)同時(shí)向后訪問，不過兩者的移動速度都為1，當(dāng)兩者再次相遇時(shí)，該相遇的節(jié)點(diǎn)即為環(huán)的起始節(jié)點(diǎn)，分析如下：

如下圖所示，假設(shè)h為鏈表頭結(jié)點(diǎn)，p為兩指針第一次相遇節(jié)點(diǎn)，m為頭結(jié)點(diǎn)到起始節(jié)點(diǎn)走過的路程（經(jīng)過的節(jié)點(diǎn)個數(shù)），n為環(huán)起始節(jié)點(diǎn)到p的路程，則對于第一次相遇有：

慢指針走過的路程：s=m+n+aC

快指針走過的路程：2s=m+n+bC

a，b分別表示兩指針相遇前第一次經(jīng)過p點(diǎn)后繞環(huán)的圈數(shù)，C表示環(huán)的長度，由于快指針的速度是慢指針的兩倍，時(shí)間一樣，故快指針走過的路程是慢指針的兩倍。

兩式相減有s=(b-a)C=m+n+a*C

故m+n恰為環(huán)長度的整數(shù)倍

慢指針從頭結(jié)點(diǎn)到起始節(jié)點(diǎn)走了m，由于同時(shí)同速度快指針也走了m，而移動前快指針距起始節(jié)點(diǎn)距離為n，m+n恰為環(huán)長度的整數(shù)倍，故快指針移動m后也到了起始節(jié)點(diǎn)，即此時(shí)相遇點(diǎn)為起始節(jié)點(diǎn)

/**
 * 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
 * @param head
 * @param kth
 * @return
 */
public static SNode getKthNode(SNode head,int kth){
    SNode temNode=head,kthNode=null;
    for(int count=1;count<kth;count++) {
        if(temNode!=null)
            temNode=temNode.getNext();
    }
    while(temNode!=null) {
        if(kthNode==null)
            kthNode=head;
        else
            kthNode=kthNode.getNext();
        temNode=temNode.getNext();
    }
    if(kthNode!=null)
        return kthNode;
    return null;
}

2.1判斷鏈表是否以null結(jié)尾,是否包含環(huán)

/**
 * 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
 * @param head
 * @return
 */
public static boolean doesLinkedListContainsLoop(SNode head) {
    if(head==null)
        return false;
    SNode fastNode=head,slowNode=head;
    while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
        slowNode=slowNode.getNext();
        fastNode=fastNode.getNext().getNext();
        if(fastNode==slowNode)
            return true;
    }
    return false;
}

2.2判斷給定的鏈表是否以null結(jié)束。如果鏈表中存在環(huán)，找到環(huán)的起始節(jié)點(diǎn)

/**
 * @param head
 * @return
 */
public static SNode findBeginOfLoop(SNode head) {
    SNode slowNode=head,fastNode=head;
    boolean loopExists=false;
    if(head==null)
        return null;
    while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
        slowNode=slowNode.getNext();
        fastNode=fastNode.getNext().getNext();
        if(slowNode==fastNode) {
            loopExists=true;
            break;
        }
    }
    if(loopExists) {  //環(huán)存在
        slowNode=head;
        while(slowNode!=fastNode) {
            slowNode=slowNode.getNext();
            fastNode=fastNode.getNext();
        }
        return slowNode;  //返回環(huán)開始節(jié)點(diǎn)
    }
    return null;  //環(huán)不存在
}

2.3判斷鏈表是否存在環(huán)，若存在，則返回環(huán)的長度，否則返回0

/**
 * @param head
 * @return
 */
public static int findLoopLength(SNode head) {
    SNode slowNode=head,fastNode=head;
    boolean loopExists=false;
    int counter=0;
    if(head==null)
        return 0;
    while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null) {
        slowNode=slowNode.getNext();
                    counter++;
        fastNode=fastNode.getNext().getNext();
        if(slowNode==fastNode) {
            loopExists=true;
            break;
        }
    }
    if(loopExists) {
        fastNode=fastNode.getNext();
        while(fastNode!=slowNode) {
            fastNode=fastNode.getNext();
            counter++;
        }
        return counter;
    }
    return 0;
}

3.將一個循環(huán)鏈表變成兩個循環(huán)鏈表

/**
 * @param head
 * @param head1
 * @param head2
 */
public static void splitList(SNode head,SNode head1,SNode head2) {
    SNode slowNode=head,fastNode=head;
    if(head==null)
        return;
    //如果循環(huán)鏈表有奇數(shù)個節(jié)點(diǎn)，則fastNode.getNext()指向head
    //如果循環(huán)鏈表有偶數(shù)個節(jié)點(diǎn)，則fastNode.getNext().getNext()指向head
    while(fastNode.getNext()!=head&&fastNode.getNext().getNext()!=head) {
        fastNode=fastNode.getNext().getNext();
        slowNode=slowNode.getNext();
    }
    if(fastNode.getNext().getNext()==head) {
        fastNode=fastNode.getNext();
    }
    //head1指向前半部分的head指針
    head1=head;
    //head2指向后半部分的指針
    if(head.getNext()!=head)
        head2=slowNode.getNext();
    //把后半部分變成環(huán)
    fastNode.setNext(slowNode.getNext());
    //把前半部分變成環(huán)
    slowNode.setNext(head);
}

4.有序鏈表中插入一個節(jié)點(diǎn)

/**
 * 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
 * @param head
 * @param newNode
 * @return
 */
public static SNode insertSortedList(SNode head,SNode newNode) {
    SNode current=head,temp=null;
    if(head==null)
        return newNode;
    while(current!=null) {
        temp=current;
        current=current.getNext();
    }
    newNode.setNext(current);
    temp.setNext(newNode);
    return head;
}

5.1鏈表逆置

/**
 * 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
 * @param head
 * @return
 */
public static SNode reverseList(SNode head) {
    SNode temp=null,nextNode=null;
    while(head!=null) {
        nextNode=head.getNext();
        head.setNext(temp);
        temp=head;
        head=nextNode;
    }
    return temp;
}

5.2逐對逆置鏈表,假如初始鏈表為1 2 3 4 x,逐對逆置后為2 1 4 3 x

/**
 * @param head
 * @return
 */
public static SNode reversePairRecursive(SNode head) {
    SNode temp;
    if(head==null||head.getNext()==null)
        return head;
    else {
        temp=head.getNext();
        head.setNext(temp.getNext());
        temp.setNext(head);
        head=temp;
        head.getNext().setNext(reversePairRecursive(head.getNext().getNext()));
        return head;
    }
}

6.判斷兩個鏈表是否相交成為一個單鏈表，若相交，得出兩鏈表的相交節(jié)點(diǎn)

/**
 * 思路：兩鏈表相交之后的長度必然相等，先獲得兩鏈表的長度，讓更長的鏈表先后移兩鏈表長度差個單位，再一起向后遍歷，直到出現(xiàn)兩節(jié)點(diǎn)相等或到達(dá)表尾
 * 時(shí)間復(fù)雜度為O(m,n),空間復(fù)雜度為O(1)
 * @param list1
 * @param list2
 * @return
 */
public static SNode findIntersectingNode(SNode list1,SNode list2) {
    int l1=0,l2=0,diff=0;
    SNode head1=list1,head2=list2;
    while(head1!=null) {
        l1++;
        head1=head1.getNext();
    }
    while(head2!=null) {
        l2++;
        head2=head2.getNext();
    }
    if(l1<l2) {
        head1=list2;
        head2=list1;
        diff=l2-l1;
    }else {
        head1=list1;
        head2=list2;
        diff=l1-l2;
    }
    for(int i=0;i<diff;i++)
        head1=head1.getNext();
    while(head1!=null&&head2!=null) {
        if(head1==head2)
            return head1;
        head1=head1.getNext();
        head2=head2.getNext();
    }
    return null;
}

7.尋找鏈表的中間節(jié)點(diǎn):設(shè)置兩個指針，第一個指針的移動速度是第二個指針的兩倍，當(dāng)?shù)谝粋€指針到達(dá)表尾，第二個指針即指向中間節(jié)點(diǎn)

/**
 * 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
 * @param head
 * @return
 */
public static SNode findMiddle(SNode head) {
    SNode point1=head,point2=head;
    int i=0;
    while(point1.getNext()!=null) {
        if(i==0) {
            point1=point1.getNext();
            i=1;
        }else if(i==1) {
            point1=point1.getNext();
            point2=point2.getNext();
            i=0;
        }
    }
    return point2;
}

8.檢查鏈表長度是奇數(shù)還是偶數(shù),每次后移兩個元素,返回1表示奇數(shù)，返回0表示偶數(shù)

/**
 * 時(shí)間復(fù)雜度為O(n/2)，空間復(fù)雜度為O(1)
 * @param head
 * @return
 */
public static int isLinkedListLengthEven(SNode head) {
    while(head!=null&&head.getNext()!=null) {
        head=head.getNext().getNext();
    }
    if(head==null)
        return 0;
    else
        return 1;
}

9.合并兩個有序鏈表

/**
 * 時(shí)間復(fù)雜度為O(n)
 * @param a
 * @param b
 * @return
 */
public static SNode mergeList(SNode a,SNode b) {
    SNode result=null;
    if(a==null)
        return b;
    if(b==null)
        return a;
    if(a.getData()<=b.getData()) {
        result=a;
        result.setNext(mergeList(a.getNext(), b));
    }else {
        result=b;
        result.setNext(mergeList(a,b.getNext()));
    }
    return result;
}

10.從表尾開始輸出鏈表

/**
 * @param head
 */
public static void printListFromEnd(SNode head) {
    if(head==null)
        return;
    printListFromEnd(head.getNext());
    System.out.println(head.getData());
}