LinkList1

发表于 更新于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/]

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

算法描述

​ 首先预防链表会删完，添加一个虚拟节点d,令d->next=head即可；要删除倒数第n个节点，因为这个链表是单链表，只能单向遍历，要实现O(n)的复杂度，得有两个节点，使他们间距为n一起向前移动，当后面节点到了尾部，前面节点就在倒数第n个节点上，然后使当前节点的next指向后面节点的next即可；

​ 时间复杂度：一次遍历O(n)

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* d = new ListNode(0);
        ListNode *frist,*second;
        d->next=head;
        frist=d;
        second=d;
        
        for(int i=0;i<n;i++)frist=frist->next;
        while(frist->next){
            frist=frist->next;
            second=second->next;
        }
        second->next=second->next->next;
       
        return d->next;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next==null||head==null)return null;
        ListNode d = new ListNode(0);
        ListNode prev=null,con=null;
        d.next = head;
        prev=con=d;
        for(int i=0;i<n;i++)prev=prev.next;
        while(prev.next!=null){
            prev=prev.next;
            con=con.next;
        }
        con.next=con.next.next;
        return d.next;
    }
}