【考研数据结构代码题2】删除单链表倒数第n个结点

结点"/>

【考研数据结构代码题2】删除单链表倒数第n个结点

题目：删除单链表倒数第n个结点

难度：★

算法思路： 首先题目没有指明链表的长度，多以首先需要编写一个函数getLength()来求表长，其次删除倒数第n个结点，即删除正数第length-n+1个结点，这是二者之间的关系，可以通过找规律归纳得到，删除单链表中某结点关键是找到该结点的前一个结点，修改指针域即可，最后释放掉被删结点所占内存，如下图所示：

//链表结点结构 
typedef struct ListNode{int val;//数据域 struct ListNode* next;//指针域 
}ListNode;//获取链表的结点数，即表长
int getLength(ListNode* head){int length=0;ListNode* p=head;//游标指针 while(p->next){length++; p=p->next;//移动到 下一个结点处 }return length;
} 
//删除链表倒数第n个结点
ListNode* deleteNode(ListNode* head,int n){int length=getLength(head);//先获取表长 ListNode* p=head;//游标指针 ListNode* temp=NULL;//临时指针//循环找到需要删除结点的前一个结点，修改相关指针域for(int i=0;i<length-n;i++){p=p->next;}temp=p->next;//保存待删结点 p->next=p->next->next;//逻辑删除free(temp);//释放结点所占内存，物理删除 return head; 
}