image.png

思路 雙指針 時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O1

1. 首先還是先設(shè)置虛擬頭節(jié)點(diǎn), 方便處理刪除頭節(jié)點(diǎn)的情況dummyHead.next = head

2. 設(shè)置fast = dummyHead, slow = dummyHead;

3. 讓fast先走N步, slow再開始走. 當(dāng)fast指向null 時(shí).說明走到了最后,此時(shí)slow的位置就是倒數(shù)第N個(gè)節(jié)點(diǎn)的位置

4. 要刪除倒數(shù)第N個(gè)節(jié)點(diǎn), 我們必須拿到N前面那個(gè)節(jié)點(diǎn) 就是N -1 ,所以我們讓fast走n+1步,當(dāng)fast走到最后時(shí), slow指向的位置就是倒數(shù)第N-1個(gè)節(jié)點(diǎn).

5. 此時(shí)我們要操作slow.next = slow.next.next即可刪除倒數(shù)第N個(gè)節(jié)點(diǎn)

6. 看到一個(gè)網(wǎng)友評(píng)論的可優(yōu)化的地方 第二層while循環(huán)有個(gè)優(yōu)化點(diǎn), 當(dāng)fast.next != null 時(shí)候. fast不用走n + 1步
   我個(gè)人覺得走n+1步好理解一點(diǎn). 這個(gè)優(yōu)化點(diǎn)剛開始我都沒看明白為啥??

    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;
        n++;
        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }
// 優(yōu)化版
    public ListNode removeNthFromEnd(ListNode head, int n) {
         ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

        while (n-- > 0 && fast != null) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return dummyHead.next;
    }