1.算法題目

給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.

說明：

給定的 n 保證是有效的。

進階：

你能嘗試使用一趟掃描實現(xiàn)嗎？

通過次數(shù)131,025提交次數(shù)3

2.算法思路

雙鏈表法：可以通過遍歷一次鏈表，也不需要計算鏈表的長度，即可找到要刪除的節(jié)點，具體思路：定義兩個鏈表 firstNode 和 secondNode ，初始化時都指向頭節(jié)點，刪除鏈表的倒數(shù)第 n 個節(jié)點時需要找到倒數(shù)第 n + 1 個節(jié)點，先遍歷 firstNode，firstNode 遍歷到 n + 1 個節(jié)點的時候再開始遍歷 secondNode，當firstNode遍歷到尾結(jié)點的時候，secondNode 剛好遍歷到倒數(shù)
n + 1 個節(jié)點的位置，此時刪除 secondNode 的下一個節(jié)點即可。需要注意的是鏈表只有一個節(jié)點的特殊情況，此時需要刪除頭節(jié)點。

3.算法代碼

根據(jù)雙鏈表法的算法思路編寫的算法Java實現(xiàn)代碼如下：

    // 鏈表定義
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode firstNode = head;
        ListNode secondNode = head;
        while (firstNode != null && firstNode.next != null) {
            firstNode = firstNode.next;
            if(n == 0) {
                secondNode = secondNode.next;
            }
            if (n > 0) {
                n --;
            }
        }
        if (n > 0) { // 刪除當前節(jié)點
            if (secondNode.next == null) { // 刪除頭節(jié)點
                head = null;
            } else {  // 刪除當前節(jié)點
                head = head.next;
            }
        } else {
            ListNode tmp = secondNode.next; // 待刪除節(jié)點
            secondNode.next = tmp.next;
        }
        return head;
    }

4.總結(jié)

雙鏈表法在有關(guān)鏈表的算法中比較常用，而且用起來很方便，比如判斷一個鏈表是否有環(huán)、刪除指定位置的節(jié)點、判斷兩個鏈表是否交叉（交叉的鏈表后面的節(jié)點都是一樣的，可以讓長度長的鏈表先走兩個鏈表長度只差的位置）等等。

附判斷兩個鏈表是否交叉的算法Java實現(xiàn)代碼：

    // 鏈表定義
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    //獲取鏈表長度
    private int getLength(ListNode head){

        int len = 0 ;
        /*
         ListNode cur = head;
         while(cur != null){
             len ++;
             cur = cur.next;
        */
        for(ListNode cur =head;cur!= null;cur = cur.next){
            len ++;
        }
        return len;
    }

    //判斷交叉+求交叉結(jié)點
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        ListNode longer = headA;
        ListNode shorter = headB;

        int diff = lenA-lenB;

        if(lenA < lenB){
            diff = lenB-lenA;
            longer = headB;
            shorter = headA;
        }

        //讓長鏈表先走diff步,保證下一步while值對比循環(huán)初始兩個鏈表長度是相同的
        for(int i = 0; i < diff; i++){
            longer =longer.next;
        }

        //循環(huán)遍歷，當值相等時停止循環(huán)
        while(longer != shorter){
            longer = longer.next;
            shorter = shorter.next;
        }
        //返回交叉結(jié)點
        return longer;
    }

??如果你有疑問或更好的算法思路，歡迎留言交流?。。?/strong>
??如果感覺我的文章對您有所幫助，麻煩動動小手給個喜歡，謝謝?。?！