《leetCode》：Remove Nth Node From End of List

本文主要是介绍《leetCode》：Remove Nth Node From End of List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Given a linked list, remove the nth node from the end of list and return its head.For example,Given linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

题目大意：删除链表的倒数第n个结点。要注意的是：n值一直是有效的。好好品味这句话。

思路如下：要删除倒数第n个结点，就是删除第（len-n+1）个结点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int my_length(struct ListNode* head){if(head==NULL)return 0;struct ListNode *node=head;int len=1;while(node->next!=NULL){len++;}return len;}//移除链表中倒数第n个结点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {if(head==NULL||n<=0){return head;}//先求链表长度int len=my_length(head);if(len<n){return head;}else if(len==n){//删除头结点head=head->next;return head;}else{//不是删除头结点，删除倒数第n个结点，即就是删除第（len-n+1）个结点int  m=len-n;struct ListNode *node=head;while(m>1){//使得node指向要删除的节点的前面一个结点node=node->next;m--;}node->next=node->next->next;}return head;}

上面的思路是如此的清晰，但是就是AC不过，报超时错误。

解决方法包括：把上面的my_length直接在函数里面实现，避免函数的调用花费太多时间，但是还是AC不过。

于是，看了下网上，别人的实现代码，
网上的实现思路如下：利用双指针思想，前后指针相隔n-1个结点，当后面的指针没有后继时，则第一个指针指向的指针就是要删除的结点。

//移除链表中倒数第n个结点。struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {if(head==NULL||n<=0){return head;}struct ListNode *pNode=head;if(n==1){//删除最后一个结点，其实这一个不要也可以，但是如果不加这一种特殊情况，连上面出现的错误都AC不过。while(pNode!=NULL){if(pNode->next==NULL){break;}pNode=pNode->next;}pNode=NULL;return head;}//先求链表长度int len=1;pNode=head;while(pNode->next!=NULL){len++;}if(len<n)return head;else if(len==n){//删除头结点head=head->next;return head;}//利用双指针else {struct ListNode *p1=head;struct ListNode *p2=head;int m=n-1;//将第一个指针移动n-1个位置while(m>0){p2=p2->next;m--;}//然后将p1,p2一起移动，直到p2的下一个结点为NULLstruct ListNode *preNode=NULL;while(p2!=NULL){preNode=p1;p1=p1->next;p2=p2->next;if(p2->next==NULL){//保证p2指向最后一个非空结点。break;}}//最后删除p1指向的节点即可preNode->next=p1->next;free(p1);p1=NULL;}return head;}

发现这样还是AC不了，这样真是要奔溃。

又看了下网上别人是怎么做的，发现都没有求链表的长度，并没有对n进行有效性检查，到这里，才终于理解了题目中的这句话：Given n will always be valid.
oh，mygod，这样将求链表长度的代码去除后，就AC了。

//移除链表中倒数第n个结点。//思路：利用双指针思想，前后指针相隔n-1个结点，当后面的指针没有后继时，则第一个指针指向的指针就是要删除的结点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {if(head==NULL||n<=0){return head;}   //利用双指针struct ListNode *p1=head;struct ListNode *p2=head;int m=n-1;//将第一个指针移动n-1个位置while(m>0){p2=p2->next;m--;}//然后将p1,p2一起移动，直到p2的下一个结点为NULLstruct ListNode *preNode=NULL;while(p2!=NULL){if(p2->next==NULL){//保证p2指向最后一个非空结点。break;}preNode=p1;p1=p1->next;p2=p2->next;}if(preNode==NULL){//此种情况说明删除的是头结点head=p1->next;}else{//最后删除p1指向的节点即可preNode->next=p1->next;}free(p1);p1=NULL;return head;}