网站首屏做多大,游戏周边产品 做网站,崇信县门户网站留言首页,wordpress客户端制作给定一个链表#xff0c;删除链表的倒数第 n 个节点#xff0c;并且返回链表的头结点。示例#xff1a;给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后#xff0c;链表变为 1-2-3-5.说明#xff1a;给定的 n 保证是有效的。题解…给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。示例给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后链表变为 1-2-3-5.说明给定的 n 保证是有效的。题解我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n1n1 步而第二个指针将从列表的开头出发。现在这两个指针被 nn 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nn 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。 删除链表的倒数第 N 个元素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;}复杂度分析时间复杂度O(L)O(L)该算法对含有 LL 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)O(L)。空间复杂度O(1)O(1)我们只用了常量级的额外空间。
