单链表之删除链表中倒数第n个节点

这篇依然是学习专栏《数据结构与算法之美》链表相关内容的拓展。

删除链表中倒数第n个节点其实有几种不同的思路，

  • 可以先遍历一遍记下每个节点的位置，最后再遍历找到倒数第n个节点进行删除

学习过时间复杂度分析的同学应该就会发现，这里要遍历两次，在最坏的情况下（要删除的是倒数第一个节点），那么消耗的时间就可以达到2T(n).

  • 使用快慢指针，快指针指向慢指针后的n个节点，然后快慢指针同时前进，直到快指针达到尾部，此时慢指针指向的next就是我们要删除的节点了。

这种方法我刚看到的时候就觉得挺巧妙的，实现也比较简单，下面附上这种解法的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    /**
     * 使用快慢指针，快指针比慢指针多n
     * 所以当快指针抵达尾部，满指针的next就是准备删除的节点
     * @param head
     * @param n
     * @return
     */
    public static ListNode deleteNodeFromBack(ListNode head, int n) {
        // 空链表
        if (head == null) {
            return null;
        }

        ListNode pSlow = head;
        ListNode pFast = head;

        for (int i = 0; i < n; i++) {
            pFast = pFast.next;
        }

        while (pFast.next != null) {
            pFast = pFast.next;
            pSlow = pSlow.next;
        }

        // 删除节点
        pSlow.next = pSlow.next.next;
//        System.out.println(pSlow);
        return head;
    }

需要注意的是：这里我有些极限情况是没有处理到的，比如n大于了整个链表的长度，为了简洁明了向大家展示这个算法的思路。