基于链表结构的基本算法题目

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

说明： 给定的 n 保证是有效的。

进阶： 你能尝试使用一趟扫描实现吗？

示例

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

考察知识点

链表的实现、双指针

核心思想

方法一：两次遍历算法

思路
我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 \((L - n + 1)\) 个结点，其中 \(L\) 是列表的长度。只要我们找到列表的长度 \(L\)，这个问题就很容易解决。

算法
首先我们将添加一个哑结点作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 \(L\)。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 \((L - n)\) 个结点那里。我们把第 \((L - n)\) 个结点的 next 指针重新链接至第 \((L - n + 2)\) 个结点，完成这个算法。

a476f4e932fa4499e22902dcb18edba41feaf9cfe4f17869a90874fbb1fd17f5-file_1555694537876.png

时间复杂度：\(O(L)\)，该算法对列表进行了两次遍历，首先计算了列表的长度 \(L\) 其次找到第 \((L - n)\) 个结点。 操作执行了 \(2L-n\) 步，时间复杂度为 \(O(L)\)。
空间复杂度：\(O(1)\)，我们只用了常量级的额外空间。

方法二：一次遍历算法

算法
上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 \(n+1\) 步，而第二个指针将从列表的开头出发。现在，这两个指针被 \(n\) 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 \(n\) 个结点。我们重新链接第二个指针所引用的结点的 \(next\) 指针指向该结点的下下个结点。

4e134986ba59f69042b2769b84e3f2682f6745033af7bcabcab42922a58091ba-file_1555694482088 1.png

复杂度分析
时间复杂度：\(O(L)\)，该算法对含有 \(L\) 个结点的列表进行了一次遍历。因此时间复杂度为 \(O(L)\)。
空间复杂度：\(O(1)\)，我们只用了常量级的额外空间。

关键思想
- 双指针的奇妙作用（利用双指针间隔进行控制） - 使用哑结点防止特殊情况

Python版本

方法一的python实现。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)  # 声明哑结点
        dummy.next = head  # 添加哑结点在head前面
        length  = 0
        first = head
        while first != None:  # 求得链表长度
            length += 1
            first = first.next
        length -= n  # 计算倒数第n个节点在正数的第几个节点
        first = dummy
        while length > 0:
            length -= 1
            first = first.next
        first.next = first.next.next  # 跳过要删除的那个节点即可

        return dummy.next

方法二的Python实现。

# Definition for singly-linked list.
class ListNode():
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return str(self.value)


def createList(value_list: list) -> ListNode:
    """
    Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return False
    if _len == 1:
        return ListNode(value_list)
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            tmp.next = ListNode(value_list[i])  # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp = tmp.next  # 更新tmp
    return root # 返回根节点


def convert2list(head: ListNode) -> list:
    """
    Convert linked list to normal list
    :param head: ListNonde
    :return: list
    """
    res = []
    p = head
    while p != None:
        # print()
        res.append(p.value)  # 由于有ListNode实现了__str__函数 就不用调用p.value来获取节点值了
        p = p.next
    return res

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        for i in range(1, n+1):
            first = first.next
        while first.next != None:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next


print("leet code accept!!!")
Input = [
    [1, 2, 3, 4, 5]
]
Input1 = [2]
Answer = [
    [1, 2, 3, 5]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        head = createList(Input[i])
        result = solution.removeNthFromEnd(head, Input1[i])
        result = convert2list(result)
        print(result)
        print(Answer[i])

有效法糖

1、单向链表的声明、初始化、插入、删除，详情见“DS_链表.md”。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None