给出一个单向链表的头指针,输出该链表中倒数第K个节点的指针
Q:给出一个单向链表的头指针,输出该链表中倒数第K个节点的指针,链表的倒数第0个节点为链表的尾节点(尾节点的next成员为NULL)
NODE* findnode(NODE *head,unsigned int k);
思路:首先求出单向链表的长度为Len,然后从链表头指针开始遍历,一直遍历Len-1-K次就可以找到倒数第K个节点指针。
代码实现如下:
1 #include 2 #include 3 4 typedef struct Node 5 { 6 int data; 7 struct Node *next; 8 }Node; 9 10 //根据提供的数据创建单链表11 Node *CreateList(int data[],int n)12 {13 assert(n>0);14 Node *head=new Node;15 head->data=data[0];16 head->next=NULL;17 18 Node *p=head;19 20 21 for (int i=1;idata=data[i];25 p1->next=NULL;26 p->next=p1;27 p=p1;28 }29 30 return head;31 }32 33 //获取单链表的长度34 int GetListLen(Node *head)35 {36 int len=0;37 while(head)38 {39 len++;40 head=head->next;41 }42 return len;43 }44 45 //选择倒数第K个节点指针46 Node *FindNode(Node *head,int k)47 {48 int len=GetListLen(head);49 if (k>len-1)50 {51 return NULL;52 }53 54 int num=len-k-1;55 Node *p=head;56 57 while(num)58 {59 p=p->next;60 num--;61 }62 return p;63 }64 65 void main()66 {67 int data[5]={1,2,3,4,5};68 Node *head=CreateList(data,5);69 int length=GetListLen(head);70 coutdata