19. 删除链表的倒数第 N 个结点


19. 删除链表的倒数第 N 个结点

链表的长度

用到哑节点
遍历到 L−n+1 个节点时,它的下一个节点就是我们需要删除的节点,只需要修改一次指针,就能完成删除操作。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) &#123;
            cur = cur.next;//知道要删除的节点的前一个
        &#125;
        cur.next = cur.next.next;
        ListNode ans = dummy.next;//保留最开始位置
        return ans;
    &#125;

    public int getLength(ListNode head) &#123;
        int length = 0;
        while (head != null) &#123;
            ++length;
            head = head.next;
        &#125;
        return length;
    &#125;
&#125;

双指针、

class Solution &#123;
    public ListNode removeNthFromEnd(ListNode head, int n) &#123;
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;//双指针错开一个位置.
        ListNode second = dummy;//
        for (int i = 0; i < n; ++i) &#123;
            first = first.next;
        &#125;
        while (first != null) &#123;//退出循环时first指向null.
            first = first.next;
            second = second.next;
        &#125;
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    &#125;
&#125;


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
7. 整数反转 7. 整数反转
7. 整数反转 考虑溢出class Solution &#123; public int reverse(int x) &#123; int ans = 0; while (x !=
2021-02-24 future
下一篇 
延长iPhone 手机电池寿命的几个方法 延长iPhone 手机电池寿命的几个方法
手机电池不耐用,很多人觉得似乎要换电池了。现在分享一波苹果电池实用技巧,可延长 iPhone 手机电池寿命哦!1.不要过夜充电锂电池充电快速,从零到充满大约只需要 1 小时。而现在的智慧型手机内建的芯片都有保护机制,一旦电量充满,便会停止充
2020-12-09
  目录