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

系统管理员 2023-01-03 06:12 103阅读 0赞

# [19. 删除链表的倒数第N个节点][19. _N] #

## 1、参考资料 ##

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

## 2、题目要求 ##

> **题目描述**

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

> **示例：**

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

> **进阶：**

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

## 3、代码思路 ##

这道题的思路和寻找链表倒数第 `N` 个节点的思路相似，使用双指针可以通过一趟遍历完成

1.  不同的是寻找链表倒数第 `N` 个节点需要定位至倒数第 `K` 个节点，而单链表的删除需要定位至待删除节点的前一个节点，即倒数第 `N+1` 个节点
2.  那么问题就来了，我如果想要删除链表的首节点怎么办？首节点可是没有前一个节点的呀，这时候头结点(`dummyHead`)就派上用场了，我们在原链表的基础上定义一个头结点 `dummyHead`，`dummyHead` 指向原链表的首节点(`head`)
3.  我们定义两个指针：`front` 指向链表前部，`behind` 指向链表后部，我们目标是当 `behind` 指向 `null` 的时候，`front` 指向倒数第 `N+1` 个节点，此时通过 `front.next =f ront.next.next` 即可删除倒数第 `N` 个节点

--------------------

边界条件的确定

1.  因为我们需要定位至倒数第 `N+1` 个节点，所以 `front` 与 `behind` 始终相差 `N+1` 个节点
2.  就拿下面的例子来说明，链表为 `1 --> 2 --> 3 --> 4 --> 5`，我们需要删除倒数第 `2` 个节点
    
        1 --> 2 --> 3 --> 4 --> 5 --> null
3.  首先我们在链表前面加一个 `dummyHead`，让 `front` 指向 `dummyHead`，让 `behind` 指向 `head`
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
            ^         ^
            |         |
           front    behind
4.  `behind` 向后移动两步，即初始化时 `behind` 指向 `head`，然后向后移动 `N` 步
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
            ^                     ^
            |                     |
           front                behind
5.  `front` 和 `behind` 一起向后移动，直至 `behind` 为空
    
        dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null
                                  ^                  ^
                                  |                  |
                                front              behind
6.  `front.next =f ront.next.next` 删除倒数第 `2` 个节点
    
        dummyHead --> 1 --> 2 --> 3 --> 5 --> null
                                  ^            ^
                                  |            |
                                front        behind

## 4、代码实现 ##

代码

static class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            // DummyHead
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
    
            ListNode front = dummyHead; // 初始化时 front 指向 dummyHead
            ListNode behind = head; // 初始化时 front 指向 head
    
            // behind 向后移动 n 步，保证 front 和 behind 相差 n+1 步
            int count = 0;
            for (; count < n && behind != null; count++) {
        
                behind = behind.next;
            }
    
            // 如果输入的 n 大于链表长度，则直接返回原链表
            if (count < n) {
        
                return head;
            }
    
            // front 和 bbehind 一起后移
            while (behind != null) {
        
                behind = behind.next;
                front = front.next;
            }
    
            // 删除倒数第 n 个节点
            front.next = front.next.next;
    
            // 返回新链表的首节点
            return dummyHead.next;
        }
    }
    
    static class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
        }
    }

[19. _N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/