筆試題&面試題：設計一個複雜度為n的算法找到單向連結清單倒數第m個元素

設計一個複雜度為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;
}
           

程式運作截圖：