Leetcode 19. 删除链表的倒数第 N 个结点

男娘i 2023-01-23 05:56 87阅读 0赞

#### 题目重述 ####

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

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

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

输入：head = \[1,2,3,4,5\], n = 2  
输出：\[1,2,3,5\]

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

输入：head = \[1\], n = 1  
输出：\[\]

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

输入：head = \[1,2\], n = 1  
输出：\[1\]

#### 提示： ####

链表中结点的数目为 sz  
1 <= sz <= 30  
0 <= Node.val <= 100  
1 <= n <= sz

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

*  这题不难，找到倒数第N+1个结点，即倒数第N个结点的前驱，就可以删除。
 *  找的话，使用双指针(快慢指针)去找。
 *  但麻烦的是，一些边界条件不容易考虑到。而涉及到删除的话，可以使用哑结点，方便操作，能够让每个几点都是有前驱的。

#### Java实现 ####

/**
     * 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 {
        
        // dummy [1]      1
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            if(head == null)
            {
        
                return head;
            }
            // 哑结点,数值初始化为0，并让其指向头节点
            ListNode dummy = new ListNode(0,head);
            // 找到倒数第K+1个结点,dummy是哑结点，在第一个数据结点之前，方便操作
            ListNode p = head,q = dummy;
            int i = n;
            while(i>0)
            {
        
                p = p.next;
                i--;
            }
            while(p!=null)
            {
        
                p = p.next;
                q = q.next;
            }
            // 删除结点
            q.next = q.next.next;
            // 返回头结点
            return dummy.next;
        }
    }