首页 > itarticle > leetcode_【19】删除链表的倒数第n个节点

leetcode_【19】删除链表的倒数第n个节点

admin 11月 14, 2020 0

1.题目描述

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

2.解题思路

双指针

(1)第一个指针curNode先走n步

(2)然后第二个指针preNode再重头跟刚刚第一个指针curNode走,直到走到尾部【preNode走了(len-N)步,即下一个节点就是要删除的节点】

(3)此时的preNode的下一个即为倒数第N个节点，将其删除即可

3.代码


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class  {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preNode = head;
        ListNode curNode = head;
        //第一个指针先走n步
        for (int i = 0; i < n; i++) {
            curNode = curNode.next;
        }
        if (curNode == null) {
            return preNode.next;
        }
        //两个指针同时走，走剩下的（Len-n）步，此时preNode的下一个就是要删除的节点
        while (curNode.next != null) {
            preNode = preNode.next;
            curNode = curNode.next;
        }
        //删除倒数第N个节点
        preNode.next = preNode.next.next;
        return head;
    }
}

4.提交记录