常考数据结构与算法:删除链表的倒数第n个节点

题目描述

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
例如，

给出的链表为:1->2->3->4->5, n= 2.删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

备注：

题目保证n一定是有效的
请给出请给出时间复杂度为O(n)的算法

 

双指针

public class RemoveNthFromEndMe {public static void main(String[] args) {RemoveNthFromEndMe removeNthFromEndMe = new RemoveNthFromEndMe();ListNode l1 = new ListNode(1);ListNode l2 = new ListNode(2);ListNode l3 = new ListNode(3);ListNode l4 = new ListNode(4);ListNode l5 = new ListNode(5);ListNode l6 = new ListNode(6);l1.next = l2;l2.next = l3;l3.next = l4;l4.next = l5;l5.next = l6;removeNthFromEndMe.removeNthFromEnd(l1,2);}/**** @param head ListNode类* @param n int整型* @return ListNode类*/public ListNode removeNthFromEnd (ListNode head, int n) {if(null == head){return null;}ListNode pre = head;ListNode post = head;// 1 2 3 4 5 6int index = 0;while(index < n){pre = pre.next;index++;}while(null != pre && pre.next != null){post = post.next;pre = pre.next;}if(null == pre){head = post.next;}else {post.next = post.next.next;}return head;} }

 

 

总结

以上是生活随笔为你收集整理的常考数据结构与算法:删除链表的倒数第n个节点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。