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

2023-11-20

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：

        1 先遍历一遍，计算链表长度，再遍历一遍，完成

        2 双指针：先后指针，先走n步，再一起走

        3 栈，先全入栈，再出栈完成

双指针：

‘

/**
 * 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) {
        //注意此链表是没有长度字段的
 
        //遍历1遍   加头节点   快慢指针，快先走n步，然后一起走
 
        ListNode l=new ListNode();
        l.next=head;
 
        ListNode slow=l;
        ListNode fast=l;
 
        for(int i=0;i<n;i++ ){
            fast=fast.next;
        }
 
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
 
        slow.next=slow.next.next;
 
        return l.next;
 
 
 
    }
}

先遍历一遍：

/**
 * 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 now=head;
        int count=0;
 
        while(now!=null){
            now=now.next;
            count++;
        }
 
        now=head;
        int x=count-n;
        for(int i=0;i<x-1;i++){
            now=now.next;
        }
 
        //删除第一个元素的情况     count==n是为了区分删除的是第二个元素的情况
       if(now==head && count==n){
           ListNode l=new ListNode();
           l.next=head;
           l.next=l.next.next;
           return l.next;
       }
 
        now.next=now.next.next;
 
        return head;
 
 
 
    }
}

栈：栈的代码简单就不写了。。。