手撕算法-删除链表的倒数第 N 个结点

描述

思路

快慢指针，快指针先走N步，走不够N步返回空。
慢指针和快指针一起走，当快指针到达终点，即快指针为null时，慢指针到达倒数第N个节点。
因为要删除倒数第N个，所以要记录之前的节点pre，假设倒数第N个节点为cur，删除操作即为：
pre.next = cur.next;
cur.next = null;

因为要返回删除后的头结点，所以假设一个虚拟头结点P，P.next = head;
初始时：pre = P，cur = pre.next;

最后返回P.next；

代码

/**
 * 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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while(n > 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        if(n != 0){
            return null;
        }

        ListNode p = new ListNode();
        p.next = head;

        ListNode pre = p;
        ListNode cur = p.next;

        while(fast != null) {
            pre = pre.next;
            cur = cur.next;

            fast = fast.next;
        }

        pre.next = cur.next;
        cur.next = null;

        return p.next;
    }
}

面试公司

阿里

原文地址：https://blog.csdn.net/weixin_43155866/article/details/136965877

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！