《cracking the coding intreview》——链表

前言

最近准备暑假回家回家修整一下,所以时间大部分用来完成项目上的工作,同时为了9月份的校招,晚上的时间我还在学习<cracking the coding intreview>,第二章链表有几个不错的题目,记录一下

单链表

题目: Implement an algorithm to find the nth to last element of a singly linked list.

译文: 实现一个算法从一个单链表中返回倒数第n个元素

思路

7个节点的示例链表图如下:

例如我们找倒数第3个节点5,有两种思路

(1)遍历一遍链表,获取链表的总数len,这样倒数第n个节点也就是正数第(len - n + 1)个节点,时间复杂度为O(2n)

(2)很tricky做法,使用两个指针p,q,p指向head节点,q先前进n个节点,然后两个指针依次指向下一个,到q为NULL时,p为倒数第n个节点,时间复杂度为O(n)

代码(c语言)

采用第二种做法,因此时间复杂度更低,而且感觉更牛逼一些

/**
 * Implement an algorithm to find the nth to last element of a singly linked list
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct link {
	int value;
	struct link *next;
} link;

/**
 * 创建单链表
 *
 * T = O(n)
 *
 */
void createLinklist(link **head, int data)
{
	link *pre, *cur, *new;
	cur = *head;
	pre = NULL;

	while (cur != NULL) {
		pre = cur;
		cur = cur->next;
	}

	new = (link *)malloc(sizeof(link));
	new->value = data;

	if (pre == NULL)
		*head = new;
	else
		pre->next = new;
}

/**
 * 打印单链表
 *
 * T = O(n)
 */
void printLinklist(link *head)
{
	while (head->next != NULL) {
		printf("%d ", head->value);
		head = head->next;
	}
	printf("%d\n", head->value);
}

/**
 * 寻找单链表倒数第m个节点
 *
 * T = O(n)
 *
 */
void findMthToLast(link *head, int m)
{
	if (head == NULL) return;
	link *s1, *s2;
	int i;
	// s1指向表头,s2指向从s1开始后m个元素的位置，然后s1与s2同时后移，到s2为NULL时停止，s1为mth to last
	s1 = s2 = head;

	for (i = 0; i < m; i ++) {
		s2 = s2->next;
	}

	while (s2 != NULL) {
		s1 = s1->next;
		s2 = s2->next;
	}

	printf("%d\n", s1->value);
}

int main(void)
{
	int i, n, m, data;
	link *head;

	while (scanf("%d", &n) != EOF) {
		for (i = 0, head = NULL; i < n; i ++) {
			scanf("%d", &data);
			createLinklist(&head, data);
		}	

		// 接收mth to last
		scanf("%d", &m);

		if (m > n) {
			printf("输入数据有误！\n");
		} else {
			printLinklist(head);
			findMthToLast(head, m);
		}
	}

	return 0;
}

循环链表

题目:给定一个循环链表,实现一个算法返回这个环开始的结点

例子:

输入 : A->B->C->D->E->C[节点C在之前已经出现过]

输出:节点C

思路

先来个图示:

参考上面的做法,我们也设置两个指针,fast和slow,first一次走两个节点,slow一次走一个节点,从head出发,最后必然在循环内某个节点相遇,我们模拟一下:

1. s->B  f->D

2. s->C  f->C

(ps:不是每次都在起始点相遇哈,这里是巧合)

保持f不动,s继续移动,记录移动的次数,当再次到达f是,当前次数即为循环的长度len

然后定义两个节点p,q,p指向表头,q向前移动len步,然后一次走到p和q相遇,此节点极为链表的循环起始节点

代码(c语言)

/**
 * Given a circular linked list, implement an algorithm which returns
 * node at the begining of the loop
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct link {
	int value;
	struct link *next;
} link;

/**
 * 创建单链表
 *
 * T = O(n)
 *
 */
void createLinklist(link **head, int data)
{
	link *cur, *pre, *new;

	cur = *head;
	pre = NULL;

	while (cur != NULL) {
		pre = cur;
		cur = cur->next;
	}

	new = (link *)malloc(sizeof(link));
	new->value = data;
	new->next = cur;

	if (pre == NULL) {
		*head = new;
	} else {
		pre->next = new;
	}
}

/**
 * 从m个节点开始构建循环链表
 *
 * T = O(n)
 *
 */
void initLoopList(link *head, int m)
{
	link *cur, *pre, *target;
	cur = head;

	while (-- m && cur != NULL) {
		cur = cur->next;
	}
	target = cur;

	while (cur != NULL) {
		pre = cur;
		cur = cur->next;
	}
	pre->next = target;
}

/**
 * 寻找循环开始点的value
 *
 * T = O(n)
 *
 */
void loopStart(link *head)
{
	link *fast, *slow, *p, *q;
	int i, len;

	for (slow = head, fast = slow->next->next; fast != slow;) {
		slow = slow->next;
		fast = fast->next->next;
	}

	for (len = 1, slow = slow->next; slow != fast; slow = slow->next) {
		len += 1;
	}

	p = q = head;
	for (i = 0; i < len; i ++) {
		q = q->next;
	}

	while (p != q) {
		p = p->next;
		q = q->next;
	}
	printf("%d\n", q->value);
}

int main(void)
{
	link *head;
	int i, n, m, data;

	while (scanf("%d", &n) != EOF) {
		// 创建单链表
		for (i = 0, head = NULL; i < n; i ++) {
			scanf("%d", &data);
			createLinklist(&head, data);
		}

		// 第m个点开始循环
		scanf("%d", &m);
		if (m > n) continue;
		initLoopList(head, m);

		// 查找循环起始节点(只提供头节点)
		loopStart(head);
	}

	return 0;
}