连绵的春雨把人困在家乡，于是我继续开始刷着算法题，通过 19. Remove 年th Node From End of List复习了一波链表的操作，这道题也是比较典型的链表问题，值得分享一下。

题目如下所示：

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:

Input: head = [1], n = 1
Output: []
Example 3:

Input: head = [1,2], n = 1
Output: [1]

简单来说，就是给一个单链表，然后给一个数字n，让我们把尾部第n个节点删除掉，然后返回这个链表的头部。具体例子如上面描述所说，这个题目写得还是比较清晰的。

如果说是给定数字n，是从链表头部开始算位置，那么这道题就非常简单，直接循环遍历到第n个节点，然后把第n个节点之前的节点的next改为第n+1个节点就行了。
但现在却是从尾部开始数n个节点，所以需要做一些处理。

最直接的思路是，把从尾部的问题变成从头部遍历的问题，从尾部开始往前第n个节点，就是从头部往后第（链表长度 - n）个节点被移除。

于是算法思路如下：

1. 通过遍历获得链表长度L1。
1. 计算出从头部开始数是第（L1 - n）个节点。
1. 用一个指针从head开始变量到第(L - n - 1)个节点，然后将它的next指向它下一个的下一个节点，完成节点移除。
1. 然后返回原来的链表的head。

用Python实现的代码如下：

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if head.next == None:
            return None
        
        current = head
        length_list = 0
        while current != None:
            length_list += 1
            current = current.next

        pos = length_list - n

        # it means that we should remove the first node
        if pos <= 0: return head.next
        
        # define the pointer to start to iterate the nodes
        moving_pointer = head;
        for i in range(pos - 1):
            moving_pointer = moving_pointer.next

        # If the node that we want to remove is not exist, just return the original list
        if moving_pointer.next == None:
            return head
        
        # Skip the deleted node
        moving_pointer.next = moving_pointer.next.next

        return head

这个方案比较符合人性，也容易想到，但是缺点是必须先遍历一遍整个链表获得链表长度，然后再移动指针到删除的那个节点之前的节点。

有没有办法不先获取链表长度，又能顺利从链表头部移动到想要删除的节点之前呢？我想起了古代小兵探路的故事，可以让一个指针先行一步，探出一条准确的步数，然后再让一个指针走L1（链表长度） - n - 1个节点就行了。

我简单绘制了一张图, 步骤如下所示：

定义一个dump节点，它的next指向head，fast和slow都指向dump。
用一个fast指针和slow指针分别进行移动，fast指针优遍历前n个节点，那么剩下没遍历的节点数量刚好就是L1 - n。
然后再继续遍历fast和slow，就能顺利遍历到第L1 - n -1个节点，然后移除掉下一个节点，然后返回修改后的list。

那么想好之后，快速写出代码：

class Solution(object):
   def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dump = ListNode(0)
        dump.next = head
        fast = dump
        slow = dump

        for i in range(n+1):
            fast = fast.next

        # move the fast to the end of the list
        while fast != None:
            fast = fast.next
            slow = slow.next
        
        if slow.next == None:
            return dump.next
        
        slow.next = slow.next.next

        return dump.next

Js版本类似：

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {

    let dump = new ListNode(0);
    dump.next = head;
    let fastPointer = dump;
    let slowPointer = dump;

    for (let i = 0; i <= n; i++) {
        fastPointer = fastPointer.next;
    }

    while(fastPointer != undefined) {
        fastPointer = fastPointer.next;
        slowPointer = slowPointer.next;
    }

    slowPointer.next = slowPointer.next.next;

    return dump.next;
};

如下图所示，这个算法的Runtime非常快，但是memory使用就比较大，毕竟用了2个指针以及dump去实现了遍历。

多种方法从尾部移除指定位置的链表节点

相关文章

热门标签

最新文章