您的位置:首页 > 科技 > IT业 > 19.删除链表的倒数第N个结点

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

2024/10/31 9:50:57 来源:https://blog.csdn.net/weixin_57865902/article/details/139534630  浏览:    关键词:19.删除链表的倒数第N个结点

·题目描述

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

·解题思路

使用快慢指针,慢指针比快指针晚出发n步.如图所示,当快指针到达链表尾部的时候,slow指针刚好到达要删除的结点的前一个结点。此时的删除语句:   slow.next = slow.next.next

·Java代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode slow = head;ListNode fast = head;if(head.next == null) return null;while(fast.next != null){fast = fast.next;if(n != 0) n --;else slow = slow.next;}slow.next = slow.next.next;return head;}
}

但是上述代码存在的问题在于,当需要删除头结点的时候出现错误。因此为了删除头结点需要创建一个dummy空结点,dummy.next = head  这时候就可以删除头结点了。

·改进代码

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode slow = dummy;ListNode fast = dummy;if(head.next == null) return null;while(fast.next != null){fast = fast.next;if(n != 0) n --;else slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com