LeetCode解题之Remove Nth Node From End of List

原题

将一个链表中的倒数第n个元素从链表中去除。

注意点：

• 不用考虑n是非法的情况
• 尽量做到只遍历一次链表

例子：

输入: list = 1->2->3->4->5, n = 2.
输出: 1->2->3->5

解题思路

基本思路就是用两个指针一前一后遍历链表，在第一指针遍历了n节点后，第二个指针开始和它同步前进。需要注意的是如果去除的正好是头节点，那情况就有些特殊，需要分类讨论。可以添加一个假的头节点，使原来的头节点也变为普通的节点，这样就不用分类了。关于节点去除，就是通过前一个节点的指针指向当前节点的后一个节点。

AC源码

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

    # Define this to check if it works well
    def myPrint(self):
        print(self.val)
        if self.next:
            self.next.myPrint()


class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return head
        dummy = ListNode(-1)
        dummy.next=head
        prev = dummy
        cur = dummy
        while prev and n >= 0:
            prev = prev.next
            n -= 1
        while prev:
            prev = prev.next
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next

if __name__ == "__main__":
    n5 = ListNode(5)
    n4 = ListNode(4)
    n3 = ListNode(3)
    n2 = ListNode(2)
    n1 = ListNode(1)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    result = Solution().removeNthFromEnd(n1, 5)
    result.myPrint()

欢迎查看我的Github来获得相关源码。