国内全屏网站有哪些,wordpress 适合程序员主题,企业所得税优惠政策2020,网站建设模式化的体现给定一个链表#xff0c;删除链表的倒数第 n 个节点#xff0c;并且返回链表的头结点。
示例#xff1a;
给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后#xff0c;链表变为 1-2-3-5.说明#xff1a;
给定的 n 保证是有效的…给定一个链表删除链表的倒数第 n 个节点并且返回链表的头结点。
示例
给定一个链表: 1-2-3-4-5, 和 n 2.当删除了倒数第二个节点后链表变为 1-2-3-5.说明
给定的 n 保证是有效的。
public class Solution {public static void main(String[] args) {// 1 - 2 - 3 - 4 - 5ListNode node1 new ListNode(1);ListNode node2 new ListNode(2);ListNode node3 new ListNode(3);ListNode node4 new ListNode(4);ListNode node5 new ListNode(5);node1.next node2;node2.next node3;node3.next node4;node4.next node5;ListNode newRoot removeNthFromEnd1(node1, 2);// ListNode newRoot removeNthFromEnd2(node1, 3);while (newRoot ! null) {System.out.println(newRoot.val);newRoot newRoot.next;}}// 方法一双指针private static ListNode removeNthFromEnd1(ListNode head, int n) {ListNode first head;ListNode second head;for (int k 0; k n; k) { // 让前一个指针先走n步first first.next;}if (first null) {return head.next; // 链表的长度刚刚好等于n头结点为要删除的节点}while (first.next ! null) { // 两个指针同时向后走直到前一个指针走到链表最后一个节点的nextfirst first.next;second second.next;}second.next second.next.next; // 将要删除节点的前一个节点指向要删除节点的后一个节点return head;}// 方法二借助栈private static ListNode removeNthFromEnd2(ListNode head, int n) {ListNode temp head;StackListNode stack new Stack();while (temp ! null) { // 先用栈存储整个链表stack.push(temp);temp temp.next;}if (stack.size() n) { // 如果栈的大小刚刚好等于n头结点为要删除的节点return head.next;}for (int k 0; k n; k) { // 逐个弹栈相当于链表从后向前遍历ListNode peek stack.pop();if (k n - 2) { // 保存要删除的节点的后一个节点temp peek;}if (k n) { // 将要删除节点的前一个节点指向要删除节点的后一个节点peek.next temp;}}return head;}}class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}
