题目

image.png

思路

  • 思路一：遍历，通过双指针，它们相差n步，当先走指针为null时，说明慢走的指针此时在删除节点上

  • 思路二：递归，递归时每次移动一个节点，需要一个全局遍历统计移动位置，当递归到最后一个节点时，我们就开始计数，当它等于n时就说明，此时节点位于要删除的节点，此时返回就跳过一个节点。换种思路理解就是递归相当于一个栈，我们一开始先遍历整个链表入栈，全部入栈结束后，再出栈，当出栈到第n个节点的时候，就跳过这个结点，重新指向另一个节点。

    代码

    1.   //1.遍历
    2.   public ListNode removeNthFromEnd(ListNode head, int n) {
    3.       if (head == null || n <= 0) return head;
    4.       ListNode dummy = new ListNode(0);
    5.       dummy.next = head;
    6.       ListNode prev = dummy, cur = head, tail = head;
    7.       for (int i = 0; i < n; i++) {
    8.           tail = tail.next;
    9.       }
    10.       while (tail != null) {
    11.           prev = cur;
    12.           cur = cur.next;
    13.           tail = tail.next;
    14.       }
    15.       prev.next = cur.next;
    16.       return dummy.next;
    17.   }    
    19.   //2.递归
    20.   int count = 0;
    21.   public ListNode removeNthFromEnd(ListNode head, int n) {
    22.       if (head == null) return head;
    23.       head.next = removeNthFromEnd(head.next, n);
    24.       count++;
    25.       if (count == n) return head.next;
    26.       return head;
    27.   }

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