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

淩亂°似流年 2024-04-07 15:28 60阅读 0赞

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

> 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

##### 示例 1： #####

![在这里插入图片描述][33e6d06e434046e98a41fe256136ccce.png]

> 输入：head = \[1,2,3,4,5\], n = 2  
> 输出：\[1,2,3,5\]

##### 示例 2： #####

> 输入：head = \[1\], n = 1  
> 输出：\[\]

##### 示例 3： #####

> 输入：head = \[1,2\], n = 1  
> 输出：\[1\]

#### 代码： ####

public class delN_list {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		ListNode l1 = new ListNode(1);
    		//l1.add(2);				//插入结点，打印
    		//l1.add(3);
    		//l1.add(4);				
    		//l1.add(5);
    		//l1.add(6);				
    		//l1.add(7);
    		l1.print();
    		System.out.println('\n');
    		ListNode l2 = removeNthFromEnd(l1,1);
    		if (l2 != null)
    			l2.print();
    		else
    			System.out.print("[]");
    	}
    	
    	public static class ListNode{
        
    		int val;
    		ListNode next;
    		ListNode(){
        }
    		ListNode(int val){
        
    			this.val = val;
    		}
    		ListNode(int val, ListNode next){
        
    			this.val = val;
    			this.next = next;
    		}
    		// 添加新的结点
    		public void add(int newval) {
        
    			ListNode newNode = new ListNode(newval);
    			if(this.next == null)
    				this.next = newNode;
    			else
    				this.next.add(newval);
    		}
    		// 打印链表
    		public void print() {
        
    			System.out.print(this.val);
    			if(this.next != null)
    				{
        
    					System.out.print("-->");
    					this.next.print();
    				}
    		}
    	}
    	
    	public static ListNode removeNthFromEnd(ListNode head,int n) {
        
    		ListNode head0 = new ListNode();//在头结点前新加一个空节点，方便处理
    		head0.next = head;
    		ListNode first = head0, last = head0;//设置双指针，一遍遍历就找到要删除的节点的位置
    		int i = 0;
    		
    		while(i<n && last.next != null) {
        
    			last = last.next;
    			i++;
    		}
    		
    		while(last.next != null) {
        
    			last = last.next;
    			first = first.next;
    		}
    		if(first != head0)//要删除的结点在第一个指针first的下一个
    			first.next = first.next.next;
    		else
    			head0 = head0.next;
    		return head0.next;
    	}
    
    }

##### 提示： #####

1 <= sz <= 30
    0 <= Node.val <= 100
    1 <= n <= sz

> 进阶：你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）  
链接：[https://leetcode.cn/problems/remove-nth-node-from-end-of-list][https_leetcode.cn_problems_remove-nth-node-from-end-of-list]  
仅供学习参考。

[33e6d06e434046e98a41fe256136ccce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/926de1224be6404483508e772e7e91cc.png
[https_leetcode.cn_problems_remove-nth-node-from-end-of-list]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list