移除倒数第N个节点

发表于 | 分类于 | 阅读次数：

题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。（给定的 n 保证是有效的）

进阶要求，只能进行一次遍历

示例

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

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

解析

如果允许超过一次遍历则只需要先遍历一遍获得链表的长度L，然后就可以将问题转化为移除正数第（L+1-n）个节点。但只允许一次遍历的话就需要使用两个指针，指针1指向头节点，指针2指向头结点后n个节点，两个指针以相同速度遍历，当指针2完成遍历时，指针1指向的就是倒数第n个节点。

代码实现

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
public class RemoveNthNode {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode node0 = new ListNode(0);//哑结点
        node0.next = head;
        ListNode node1 = new ListNode(0);//指针1
        node1 = node0;
        ListNode node2 = new ListNode(0);//指针2
        node2 = node0;
        for (int i = 0; i < n; i++){
            node2 = node2.next;
        }
        while(node2.next != null){
            node1 = node1.next;
            node2 = node2.next;
        }
        node1.next = node1.next.next;//删除该节点
        return node0.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next =  new ListNode(2);
        head.next.next =  new ListNode(3);
        head.next.next.next =  new ListNode(4);
        head.next.next.next.next =  new ListNode(5);

        ListNode result = RemoveNthNode.removeNthFromEnd(head,2);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }
    }
}

该实现方案时间复杂度取决于链表长度L，只有一次遍历所以为O(L)，空间复杂度为O(1)。