删除链表的倒数第n个节点

题目描述：

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

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

备注：

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

思路分析：

时间复杂度为O(n)，最优解法是链表遍历一遍，因为链表是单向的，在遍历的过程中需要找到所需要的删除的节点位置。

可以使用两个指针，在移动的过程中一个负责找到最后一个节点，一个负责倒数第n个节点之前的节点，因此两个指针相差的节点长度就是n

typedef struct node
{int          value;struct node* next;
} list_node;void free_node_remove(list_node* remove)
{if (remove) {delete remove;}
}list_node* remove_N_note(list_node* head, int n)
{list_node* before = head;list_node* after  = head;list_node* remove = NULL;while (before) {before = before->next;if (n-- < 0) {after = after->next;}}if (n > 0) {printf("param n is invalid.\n");return head;} else if (n == 0) {remove = after;head   = after->next;} else {remove = after->next;after->next = remove->next;}free_node_remove(remove);return head;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！