力扣-19题（Java）-链表删元素

r囧r小猫 2023-01-21 14:20 6阅读 0赞

题目链接：[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 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 pre=head;
            int len=0;
    		//tip: 对于如果链表头节点会发生变动，常用手法：加一个虚拟头节点。这个程序中未使用
            //计算链表中节点的数量
            while(pre!=null){
        
                len++;
                pre=pre.next;
            }
    
            if(len==1&&n==1) return null;  //特殊情况判断 1、链表中只有一个情况
            if(len-n-1<0) return head.next;//特殊情况判断 2、要删除的是首个节点
    
            pre=head;
            for(int i=0;i<len-n-1;i++)//循环到达待处理的节点处
                pre=pre.next;
    
            if(pre.next==null) pre=null;//判断要删掉的节点是否为最后一个节点
            else pre.next=pre.next.next;
    
            return head;
        }
    }

解法二：双指针法

/**
     * 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) {
        
            //tip:
            //1、头节点可能发生变动，增加一个虚拟节点
            //2、双指针间隔n个节点，后一个节点就先走i=0;i<=n;i++次数
            ListNode dummyhead=new ListNode(0);
            dummyhead.next=head;
    
            //双指针法，建立两个指针
            ListNode p=dummyhead;
            ListNode q=dummyhead;
            
            //0(虚拟)->1->2->3->4->5->null  n=2
            //4:0  5:1  null:2
            for(int i=0;i<=n;i++)
                q=q.next;
    
            while(q!=null){
        
                p=p.next;
                q=q.next;
            }
    
            p.next=p.next.next;//删除当前节点
    
            return dummyhead.next;
    
        }
    }

[https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221020/20f22a6fe0ce452fbbf167b424fc727e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221020/1be7359909664b499afaba78e78ea491.png