【Check 42】2024-04-01 - 19. 删除链表的倒数第 N 个结点

[larscheng]

19. 删除链表的倒数第 N 个结点

[larscheng]

思路

• 方法一：先统计链表长度，删除倒数第n个节点，在已知总长度的情况下，遍历到第length-n个节点，修改指针

• 方法二：双指针，快慢指针间隔n，两个指针一起向后移动，当快指针到达链表尾部时，慢指针即为待更新处

  代码

  
  
  class Solution1 {
      public ListNode removeNthFromEnd(ListNode head, int n) {
          int length = 0;
          ListNode cur = head;
          while (cur != null ) {
              cur = cur.next;
              length++;
          }
          ListNode dummy  = new ListNode(0,head);
          cur = dummy;
          for (int i = 1; i <= length-n ; i++) {
              cur = cur.next;
          }
          cur.next = cur.next.next;
          return dummy.next;
      }
  }

```java
class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy  = new ListNode(0,head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

复杂度

• 时间复杂度：O(length)
• 空间复杂度：O(1)