前言
最近准备暑假回家回家修整一下,所以时间大部分用来完成项目上的工作,同时为了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
", 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
", 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("输入数据有误！
");
} 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
", 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;
}