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

第21天

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

难度中等1475收藏分享切换为英文接收动态反馈

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

遍历

/** * 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 a = new ListNode(0);
        a.next = head;
        ListNode p = a;
        int len = 0;
        while(p.next!=null){
    
            len++;
            p = p.next;
        }
        int t = len - n+1;
        p = a;
        for(int i=0;i<len;i++){
    
            if(i==t-1){
    
                p.next = p.next.next;
            }
            p=p.next;
        }
       
     
        return a.next;
        
    }
}

快慢指针

class Solution {
    
    public ListNode removeNthFromEnd(ListNode head, int n) {
    
        
        ListNode a = new ListNode(0);
        a.next = head;
        ListNode p = a;
        ListNode q = a;
        for(int i=0;i<n;i++) p = p.next;
        while(p.next!=null){
    
            p = p.next;
            q = q.next;
        }
        q.next = q.next.next;
        return a.next;

    }
}

栈

class Solution {
    
  public ListNode removeNthFromEnd(ListNode head, int n) {
    
    ListNode dummy = new ListNode(0, head);
    Deque<ListNode> stack = new LinkedList<ListNode>();
    ListNode cur = dummy;
    while (cur != null) {
    
      stack.push(cur);
      cur = cur.next;
    }
    for (int i = 0; i < n; ++i) {
    
      stack.pop();
    }
    ListNode prev = stack.peek();
    prev.next = prev.next.next;
    ListNode ans = dummy.next;
    return ans;
  }
}

​