[数据结构与算法]LeetCode 算法学习记录 链表 移移除链表的倒数第n个节点

public class Remove_Nth_Node_From_End_of_List {
    //Remove Nth Node From End of List
    //移移除链表的倒数第n个节点
    //Given the head of a linked list, remove the nth node from the end of the list and return its head.
    //给出一个链表的头部,移除链表的倒数第n个节点,并返回头结点

    //思路分析,因为是移除倒数第个节点,所以应该从后遍历n个节点,而且n移除的节点可以是头结点,
    //所以初步分析有俩个难点,1.如何从后遍历,2.如何处理头结点的移除,
    //初步解决思路,1.采用递归从后往前遍历,2.添加虚拟头结点代替头节点
    //注意本题中n的输入均为合法输入,不会大于链表长度,所以无需判断n的合法性,
    //从后往前的递归,先递归找到链表最后一个元素,然后再慢慢往前找第n个元素
    //注意返回的是头节点的话,还需要判断删除的是否为头结点,也不难,直接判断删除节点的前驱即可,如果前驱等于虚拟头结点则删除的就是头结点
    //代码编写
    //注意点,
    static int i = 0;
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(0,head); //创建虚拟头结点,next指向实际头结点
        ListNode pre = removeNode(temp, n);//调用方法
        if (pre == temp) {//如果删除节点的前驱等于虚拟节点,那么删除的节点就是头结点,反之删除的就不是头结点
            return pre.next;//删除头结点后返回虚拟节点的下一个即可,
        } else return head;//删除的不是头结点,就直接返回头结点,
    }

    public static ListNode removeNode(ListNode temp, int n) {
        if (temp.next == null) {//判断是否找到了最后一个元素
            return temp;//找到返回
        }//没找到向后移动
        ListNode pre = temp;//记录现在的节点,即待删除节点的子节点
        temp = temp.next;//向后移动
        removeNode(temp, n);//递归继续找最后一个节点,找到后会直接返回,不会在继续递归,走向下一步
        i++;//找到最后一个节点后,开始计数
        if (i == n) {//小于n时继续向前找,等于n时删除,大于n时会慢慢退出,这里理解比较困难,多想一想就好了
            pre.next = temp.next;//前面记录了待删除节点的前驱,所以直接删除即可
        }
        return pre;//返回删除节点的前驱
    }

    public static void main(String[] args) {
        ListNode h2 = new ListNode(2);
        ListNode h1 = new ListNode(1,h2);
        removeNthFromEnd(h1, 2);
    }

    //方法二双指针
    //一种思路比上面简单的代码
    //前后俩个指针遍历,俩个指针相距为n
    //然后一起移动,之后后指针指向null后,那么前指针就直接指向应该删除元素\
    //因为要方便删除,所以俩指针之间相距n+1举例,这样慢指针就会指向待删除节点的前驱,更方便删除
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(-1,head);//虚拟头结点

        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- >= 0) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }

}