写点什么

19. 删除链表的倒数第 N 个数(链表)

用户头像
黄敏
关注
发布于: 刚刚

思路

快慢指针,快指针先走 n 步,然后快慢一起同步。当慢指针 next 为空,则快指针的下一个就是要删除的元素。

复杂度分析

  • 时间复杂度:O(L),其中 L 是链表的长度。

  • 空间复杂度:O(1)。

代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        ListNode realHead = new ListNode(0, head);        ListNode fast = realHead;        ListNode slow = realHead;         int i = 0;        while(fast != null){            if(i <= n){                fast = fast.next;                i++;                continue;            }            fast = fast.next;            slow = slow.next;        }        slow.next = slow.next.next;         return realHead.next;    }}
复制代码


用户头像

黄敏

关注

还未添加个人签名 2019.11.30 加入

还未添加个人简介

评论

发布
暂无评论
19. 删除链表的倒数第N个数(链表)