36. Delete the penultimate node of the linked list

The first 21 God

19. Delete the last of the linked list N Nodes

Medium difficulty 1475 Switch to English to receive dynamic feedback

I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .

** Advanced ：** Can you try a scan implementation ？

Example 1：

 Input ：head = [1,2,3,4,5], n = 2
 Output ：[1,2,3,5]

Example 2：

 Input ：head = [1], n = 1
 Output ：[]

Example 3：

 Input ：head = [1,2], n = 1
 Output ：[1]

Traverse

/** * 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;
        
    }
}

Speed pointer

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;

    }
}

Stack

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;
  }
}

​