Fork me on GitHub

LeetCode-18：删除链表的倒数第N个节点

发表于

本题为LeetCode中第18道题

如果是之前没做过之类的题型的话可能一下子会蒙住，尤其是用Java语言来写的时候，所以我们要尽可能的多做这类题，多刷才能有质的飞跃

删除链表的倒数第N个节点

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

解题思路：


本题的解题思路就是典型的双指针法解题。



即让第一个指针 first 首先指向首节点，然后让其向后移动 n 个位置，然后让两一个节点 end 也指向首节点，然后循环往后遍历，每次遍历的时候 first 指针和 end 指针都向后移动，直到first指针移到最后一个节点，也就是 first.next==null 的时候就遍历完了。


这个时候你会发现， end 指针指向的是你要删除的节点的前一个节点，所以，只需要将 end 所指向的 next 的值改为 end.next.next 也就是改为我们要删除的节点的后面的节点，你看 end.next 是不是我们需要删除的节点的地址，那再往后( end.next.next )就是我们要删除的节点的后一个节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @author RickYinPeng
 * @ClassName Y_18_删除链表的倒数第N个节点
 * @Description LeetCode中第18道题
 * @date 2018/11/20/13:02
 */
public class Y_18_删除链表的倒数第N个节点 {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode listNode = removeNthFromEnd(l1, 2);

    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = head;
        ListNode end = head;

        //让first指针向前移动
        int count = 0;
        while (count!=n){
            first = first.next;
            count++;
        }

        //如果删除的是链表中的第一个元素
        if(first==null){
            return head.next;
        }

        while(first.next!=null){
            first = first.next;
            end = end.next;
        }

        end.next = end.next.next;

        return head;
    }
}