leetcode:19.删除链表的倒数第N个节点

Dear 丶 2022-02-25 12:26 166阅读 0赞

### 题目描述： ###

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

##### 示例： #####

给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后，链表变为 1->2->3->5.

###### 说明： ######

给定的 n 保证是有效的。

##### 题目难度：中等 #####

##### 分析： #####

题目已经给出了链表类，此链表比较简单，是个单链表，并且还有一个构造方法。链表是数据结构中比较常见的一种，优点就是增删比较快，对于这题来说，题目的要求是`删除倒数第N个节点`，所以我们只需要找到倒数第N个节点在哪，然后把它的前一个节点指向它的后一个节点，即可删除此节点。那么问题就是我们究竟怎么才能准确的找到这个节点呢？其实我们只需要用两个指针即可，让他们之间保持恒定的N个距离，然后把其中一个移动到最后的null节点，那么另一个就在倒数第N+1的节点位置了。  
代码如下：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode removeNthFromEnd(ListNode head, int n) { 
        	// 定义一个空节点作为结果，并且指向head节点
            ListNode res = new ListNode(0);
            res.next = head;
            // 用两个指针分别指向res节点
            ListNode p = res;
            ListNode q = res;
            // 利用循环让p指针移动N+1次，因为此时的p是指向res的，所以移动N+1次就是正数第N个节点（下标从0开始）
            // 这样的话p和q之间就间隔了N个节点
            for (int i = 0; i < n + 1; i ++) { 
                p = p.next;
            }
            // 让p指针指向链表的最后一位的下一位（就是指向null）
            // 因为p和q是同时移动的，那么此时的q指针就指向了倒数第N+1位（下标从1开始）
            while (p != null) { 
                p = p.next;
                q = q.next;
            }
            // 这时只要把q指针的next位指向下下一位就可以跳过这个倒数第N位啦。
            q.next = q.next.next;
            return res.next;
        }
    }

这里借用一下leetcode官方题解的图，让大家更容易理解。  
![链表操作图解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjA1MzU2_size_16_color_FFFFFF_t_70]

##### 总结： #####

时间复杂度为 O ( n ) O(n) O(n)，n为链表的节点个数，这里只进行了一次遍历。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjA1MzU2_size_16_color_FFFFFF_t_70]: /images/20220225/2c4f2a7176e742419e9832f76452fd34.png