怎样免费个人网站建设,怎么样推广自己的网站,徐州不锈钢网架公司,如何免费建站【力扣】19. 删除链表的倒数第 N 个结点
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2 输出#xff1a;[1,2,3,5] 示例 2#xff1a; 输入#xff1a;head [1], n…【力扣】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]
提示 链表中结点的数目为 sz 1 sz 30 0 Node.val 100 1 n sz
题解
方法一两次遍历
先遍历一次链表求出链表的总长度。根据总长度 length 的值-n就算出需要再遍历多少个节点找到要删除的节点的前一个节点 x。将 x 节点的 next 指针指向下下一个节点就可以删除节点了。
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 class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if (head null || n 0) {return head;}//增加一个特殊节点方便边界处理ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode cur dummyNode;//第一次遍历计算链表总长度int length 0;while (cur.next ! null) {cur cur.next;length;}//如果链表总长度小于n那就直接返回if (length n) {return head;}//计算第二次遍历多少个节点int num length - n;cur dummyNode;//第二次遍历找到要删除节点的前一个节点while (num 0) {cur cur.next;--num;}//删除节点并返回cur.next cur.next.next;return dummyNode.next;}
}方法二一次遍历快慢指针
需要两个指针 slow 和 fast。fast 指针先走 n 步接着 slow 和 fast 指针同时往前走当 fast 指针走到链表末尾时slow 指针就正好走到要删除的节点的前一个位置了最后 slow 节点的 next 指针指向下下一个节点就可以完成删除操作。
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 class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//增加一个特殊节点方便边界判断ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode slow dummyNode;ListNode fast dummyNode;//第一个循环fast 指针先往前走n步while (n 0 fast ! null) {fast fast.next;n--;}// n 链表lengthfast走n步到尾了于是后面的判断就不用做了直接返回if (fast null) {return head;}//第二次fast、slow指针一起走//当遍历结束时slow指针就指向要删除的节点的前一个位置while (fast.next ! null) {slow slow.next;fast fast.next;}//删除节点并返回slow.next slow.next.next;return dummyNode.next;}
}
