LeetCode 19. 删除链表的倒数第 N 个结点(java)

目录

题目描述:

代码:

第一种:

第二种:

题目描述:

给你一个链表，删除链表的倒数第 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]

代码:

第一种:

递归

public ListNode removeElements1(ListNode head, int n)
    {
         ListNode s=new ListNode(-1,head);
         recursion(s, n);
         return s.next;
    }
    private int recursion(ListNode p, int n){
        if(p == null)
            return 0;
        int nth=recursion(p.next, n); //下一个节点的返回值
        if(nth == n)//p是当前节点
            p.next=p.next.next;
        return nth+1;//当前节点的值
    }

第二种:

 public ListNode removeElements(ListNode head, int n){
        ListNode s=new ListNode(-1,head);
        ListNode p1=s;
        ListNode p2=s;
        for(int i=0;i<n+1;i++){//先让p2走到n+1个位置
            p2=p2.next;
        }
        while(p2!=null){//同时移动
            p1=p1.next;
            p2=p2.next;
        }
        p1.next=p1.next.next;
        return s.next;
    }