19. Remove Nth Node From End of List

Leetcode

题目

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

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

中文版题目

Note:

Given n will always be valid. Try to do this in one pass.

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

例子：

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

注意点：

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

思路

首先最简单的方法当然是两次遍历链表，第一次遍历计算链表元素个数，第二次遍历达到目标节点。

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

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

        # 计算链表长度
        linked_list = head
        count = 1
        while linked_list.next:
            linked_list = linked_list.next
            count += 1

        location = count - n
        if location == 0:
            head = head.next
            return head

        before = head
        count = 1
        while count < location:
            before = before.next
            count += 1

        before.next = before.next.next

        return head     

一次遍历的基本思路就是用两个指针一前一后遍历链表，在第一指针遍历了$n$节点后，第二个指针开始和它同步前进。

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

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

        linked_list = head
        count = 0
        while linked_list.next:
            linked_list = linked_list.next
            count += 1
            if count == n:
                to_remove = head
            elif count > n:
                to_remove = to_remove.next 


        if count +1 == n:
            # 移除首节点
            head = head.next
        elif not to_remove.next:
            # 移除末尾节点
            to_remove.next = None
            print("sf")

        else:
            to_remove.next = to_remove.next.next

        return head

Your runtime beats 100.00 % of python3 submissions.