设计一个复杂度为n的算法找到单向链表倒数第m个元素.最后一个元素假定是倒数第0个.

提示:双指针查找

相对于双向链表来说,单向链表仅仅能从头到尾依次訪问链表的各个节点,所以假设要找链表的倒数第m个元素也仅仅能从头到尾进行查找,在查找的过程中,设定两个指针,当中p指针指向当前訪问的节点,q指针指向p之前的节点,且两者之间相距m个节点,这样,当p指针指向最后一个节点时,那q指针指向的元素就是倒数第m个元素,程序的处理步骤例如以下:

#include <stdio.h>

#include <malloc.h>

#define	NULL	0

typedef struct node

{

	int data;

	struct node *next;

}ElemSN;

void create_link(ElemSN *head, int num[], int len)

{

	int i;

	for(i = 0; i < len; i ++)

	{

		head->next = (ElemSN *)malloc(sizeof(ElemSN));

		head->next->data = num[i];

		head->next->next = NULL;

		head = head->next;

	}

}

void find_mlink(ElemSN *head, int m) /*最后一个单元为倒数第0个单元*/

{

	ElemSN *p, *q;

	int count = 0;

	for(q = head, p = head->next; p; p = p->next)

	{

		count ++;

		if(count > m)

		{

			q = q->next;

		}

	}

	printf("The bottom number %d is: %d.\n", m, q->data);

}

void clear_link(ElemSN *head)

{

	ElemSN *p, *q;

	for(q = head, p = head->next; p; q = p, p = p->next)

	{

		free(q);

	}

	free(q);

}

int main()

{

	ElemSN *head;

	int num[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

	head = (ElemSN *)malloc(sizeof(ElemSN));

	head->data = NULL;

	head->next = NULL;

	create_link(head, num, 10);

	find_mlink(head, 3); /*查找倒数第3个单元的值*/

	clear_link(head);

	head = NULL;

	return 0;

}

程序执行截图：