Leetcode学习笔记-19-删除链表的倒数第N个节点

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

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

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

解题思路：

一趟扫描思路：用两个指针，先让其中一个指针移动n步，然后两个指针同时后移，这样，当第一个指针移动到了最后一个节点，另一个指针刚好移动到待删除节点的前一个结点。（因为最后一个节点是倒数第一个节点）

Java：

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode newHead = new ListNode(1024);
    newHead.next = head;
    ListNode slow = newHead, fast = newHead;
    while (fast.next != null) {
        if (n <= 0)
            slow = slow.next;
        fast = fast.next;
        n--;
    }
    slow.next = slow.next.next;
    return newHead.next;
}

Python：

def removeNthFromEnd(self, head, n):
    """
    :type head: ListNode
    :type n: int
    :rtype: ListNode
    """
    newHead = ListNode(1024)
    newHead.next = head
    fast = slow = newHead
    while fast.next:
        if n <= 0:
            slow = slow.next
        fast = fast.next
        n -= 1
    slow.next = slow.next.next
    return newHead.next

赏

谢谢老板！

支付宝

微信