本文主要是介绍《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;}
小结
这个题目的算法思想相当简单,但是却花费了我一个多小时时间,实在是惭愧,但是这个题目也不太好,算法应该培养我们的是严谨的思维逻辑,怎么可以有这样一句话呢?
Given n will always be valid.
哎,经过这次之后,我又明白了一个道理,需求才是王道呀
这篇关于《leetCode》:Remove Nth Node From End of List的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!