19. Remove Nth Node From End of List

题目描述:

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

Example 1:

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:

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

题目翻译

给定一个排好序的链表,删除从后往前数的第n个节点并且返回删除后的链表头指针。

示例1:

给定的链表:1->2->3->4->5,n = 2
删除倒数第2个节点后的链表:1->2->3->5

注意:

  1. 给定的链表总是正确的
  2. 在一次遍历中完成操作

解题方案

标签: Linked List

思路:

  • 本题需要维护两个指针,pre和end。一开始初始化时使得pre指针指向链表头节点,end指针指向pre+n的节点位置。然后同时往后移动pre和end指针位置,使得end指针指向最后一个节点,那么pre指针指向的则是end-n的节点位置(即倒数第n个元素的前一个节点),则将其删除。
  • 链表长度为n时,算法复杂度O(n)。

代码:

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


class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        pre = head
        end = head
        for _ in range(n):
            end = end.next
        if end is None:  # 需要删除的节点为第一个节点时,即返回第二个节点为头节点的链表
            return head.next
        while end.next is not None:
            pre = pre.next
            end = end.next
        pre.next = pre.next.next 
        return head

参考资料

results matching ""

    No results matching ""