题目描述

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

我的解法——两遍循环（AC）

链表的移动
注意删除第一个数时，是边界情况，要特判！！！
时间空间复杂度均为O(1)。
Beat96%

# 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
        """
        now = head
        count = 0
        while(now != None):
            count += 1
            now = now.next

                
        n = count - n
        if(n == 0):
            return head.next
        
        now = head
        count = 1
        while(now != None):
            if(count == n):
                now.next = now.next.next
            count += 1
            now = now.next
        return head

最优解法——一遍循环

使用两个指针cur、pre，其中cur比pre先行n步，当cur到达末尾时，pre所指的下一个元素即是要删除的元素。
一趟循环

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}