数据结构和算法面试题系列-链表
0 概述
链表作为一种基础的数据结构，在很多地方会用到。如在Linux内核代码，redis源码，python源码中都有使用。除了单向链表，还有双向链表，本文主要关注单向链表(含部分循环链表题目，会在题目中注明，其他情况都是讨论简单的单向链表)，双向链表下一篇讨论。
1 定义
先定义一个单向链表结构，如下，定义了链表结点和链表两个结构体。这里我没有多定义一个链表的结构体，保存头指针，尾指针，链表长度等信息，目的也是为了多练习下指针的操作。
// aslist.h// 链表结点定义
typedef struct ListNode {struct ListNode *next;int value;
} listNode;
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PfeF6Pp6-1682156358128)(null)]
2 基本操作
在上一节的链表定义基础上，我们完成几个基本操作函数，包括链表初始化，链表中添加结点，链表中删除结点等。
/*** 创建链表结点*/
ListNode *listNewNode(int value)
{ListNode *node;if (!(node = malloc(sizeof(ListNode))))return NULL;node->value = value;node->next = NULL;return node;
}/*** 头插法插入结点。*/
ListNode *listAddNodeHead(ListNode *head, int value)
{ListNode *node;if (!(node = listNewNode(value)))return NULL;if (head) node->next = head;head = node;return head;
}/*** 尾插法插入值为value的结点。*/
ListNode *listAddNodeTail(ListNode *head, int value)
{ListNode *node;if (!(node = listNewNode(value)))return NULL;return listAddNodeTailWithNode(head, node);
}/*** 尾插法插入结点。*/
ListNode *listAddNodeTailWithNode(ListNode *head, ListNode *node)
{if (!head) {head = node;} else {ListNode *current = head;while (current->next) {current = current->next;} current->next = node;}return head;
}/*** 从链表删除值为value的结点。*/
ListNode *listDelNode(ListNode *head, int value)
{ListNode *current=head, *prev=NULL;while (current) {if (current->value == value) {if (current == head)head = head->next;if (prev)prev->next = current->next;free(current);break;}prev = current;current = current->next;}return head;
}/*** 链表遍历。*/
void listTraverse(ListNode *head)
{ListNode *current = head;while (current) {printf("%d", current->value);printf("->");current = current->next;if (current == head) // 处理首尾循环链表情况break;}printf("NULL\\n");
}/*** 使用数组初始化一个链表，共len个元素。*/
ListNode *listCreate(int a[], int len)
{ListNode *head = NULL;int i;for (i = 0; i < len; i++) {if (!(head = listAddNodeTail(head, a[i])))return NULL;}return head;
}/**
* 链表长度函数
*/
int listLength(ListNode *head)
{int len = 0;while (head) {len++;head = head->next;}return len;
}
3 链表相关面试题
3.1 链表逆序
题： 给定一个单向链表 1->2->3->NULL，逆序后变成 3->2->1->NULL。
解： 常见的是用的循环方式对各个结点逆序连接，如下：
/*** 链表逆序，非递归实现。
*/
ListNode *listReverse(ListNode *head)
{ListNode *newHead = NULL, *current = head;while (current) {ListNode *next = current->next;current->next = newHead;newHead = current;current = next;}return newHead;
}
如果带点炫技性质的，那就来个递归的解法，如下：
/*** 链表逆序，递归实现。*/
ListNode *listReverseRecursive(ListNode *head)
{if (!head || !head->next) {return head;}ListNode *reversedHead = listReverseRecursive(head->next);head->next->next = head;head->next = NULL;return reversedHead;
}
3.2 链表复制
题： 给定一个单向链表，复制并返回新的链表头结点。
解： 同样可以有两种解法，非递归和递归的，如下：
/*** 链表复制-非递归*/
ListNode *listCopy(ListNode *head)
{ListNode *current = head, *newHead = NULL, *newTail = NULL; while (current) {ListNode *node = listNewNode(current->value);if (!newHead) { // 第一个结点newHead = newTail = node;} else {newTail->next = node;newTail = node;}current = current->next;}return newHead;
}/*** 链表复制-递归*/
ListNode *listCopyRecursive(ListNode *head)
{if (!head) return NULL;ListNode *newHead = listNewNode(head->value);newHead->next = listCopyRecursive(head->next);return newHead;
}
3.3 链表合并
题： 已知两个有序单向链表，请合并这两个链表，使得合并后的链表仍然有序（注：这两个链表没有公共结点，即不交叉）。如链表1是 1->3->4->NULL，链表2是 2->5->6->7->8->NULL，则合并后的链表为 1->2->3->4->5->6->7->8->NULL。
解： 这个很类似归并排序的最后一步，将两个有序链表合并到一起即可。使用2个指针分别遍历两个链表，将较小值结点归并到结果链表中。如果一个链表归并结束后另一个链表还有结点，则把另一个链表剩下部分加入到结果链表的尾部。代码如下所示：
/*** 链表合并-非递归*/
ListNode *listMerge(ListNode *list1, ListNode *list2)
{ListNode dummy; // 使用空结点保存合并链表ListNode *tail = &dummy;if (!list1)return list2;if (!list2)return list1;while (list1 && list2) {if (list1->value <= list2->value) {tail->next = list1;tail = list1;list1 = list1->next;} else {tail->next = list2;tail = list2;list2 = list2->next;}}if (list1) {tail->next = list1;} else if (list2) {tail->next = list2;}return dummy.next;
}
当然，要实现一个递归的也不难，代码如下：
ListNode *listMergeRecursive(ListNode *list1, ListNode *list2)
{ListNode *result = NULL;if (!list1)return list2;if (!list2)return list1;if (list1->value <= list2->value) {result = list1;result->next = listMergeRecursive(list1->next, list2);} else {result = list2;result->next = listMergeRecursive(list1, list2->next);}return result;
}
3.4 链表相交判断
题： 已知两个单向链表list1，list2，判断两个链表是否相交。如果相交，请找出相交的结点。
解1： 可以直接遍历list1，然后依次判断list1每个结点是否在list2中，但是这个解法的复杂度为 O(length(list1) * length(list2))。当然我们可以遍历list1时，使用哈希表存储list1的结点，这样再遍历list2即可判断了，时间复杂度为O(length(list1) + length(list2))，空间复杂度为 O(length(list1))，这样相交的结点自然也就找出来了。当然，找相交结点还有更好的方法。
解2： 两个链表如果相交，那么它们从相交后的节点一定都是相同的。假定list1长度为len1，list2长度为len2，且 len1 > len2，则我们只需要将 list1 先遍历 len1-len2个结点，然后两个结点一起遍历，如果遇到相等结点，则该结点就是第一个相交结点。
/*** 链表相交判断，如果相交返回相交的结点，否则返回NULL。*/
ListNode *listIntersect(ListNode *list1, ListNode *list2)
{int len1 = listLength(list1);int len2 = listLength(list2);int delta = abs(len1 - len2);ListNode *longList = list1, *shortList = list2;if (len1 < len2) {longList = list2;shortList = list1;}int i;for (i = 0; i < delta; i++) {longList = longList->next;}while (longList && shortList) {if (longList == shortList)return longList;longList = longList->next;shortList = shortList->next;}return NULL;
}
3.5 判断链表是否存在环
题： 给定一个链表，判断链表中是否存在环。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RnnPfo6y-1682156357992)(null)]
解1： 容易想到的方法就是使用一个哈希表记录出现过的结点，遍历链表，如果一个结点重复出现，则表示该链表存在环。如果不用哈希表，也可以在链表结点 ListNode 结构体中加入一个 visited字段做标记，访问过标记为1，也一样可以检测。由于目前我们还没有实现一个哈希表，这个方法代码后面再加。
解2： 更好的一种方法是Floyd判圈算法，该算法最早由罗伯特.弗洛伊德发明。通过使用两个指针fast和slow遍历链表，fast指针每次走两步，slow指针每次走一步，如果fast和slow相遇，则表示存在环，否则不存在环。(注意，如果链表只有一个节点且没有环，不会进入while循环)
/*** 检测链表是否有环-Flod判圈算法* 若存在环，返回相遇结点，否则返回NULL*/
ListNode *listDetectLoop(ListNode *head)
{ListNode *slow, *fast;slow = fast = head;while (slow && fast && fast->next) {slow = slow->next;fast = fast->next->next;if (slow == fast) {printf("Found Loop\\n");return slow;}}printf("No Loop\\n");return NULL;
}void testListDetectLoop()
{printf("\\nTestListDetectLoop\\n");int a[] = {1, 2, 3, 4};ListNode *head = listCreate(a, ALEN(a));listDetectLoop(head);// 构造一个环head->next->next->next = head;listDetectLoop(head);
}
扩展： 检测到有环的话，那要如何找链表的环的入口点呢？
首先，我们来证明一下为什么上面的解2提到的算法是正确的。如果链表不存在环，因为快指针每次走2步，必然会比慢指针先到达链表尾部，不会相遇。
如果存在环，假定快慢指针经过s次循环后相遇，则此时快指针走的距离为 2s，慢指针走的距离为 s，假定环内结点数为r，则要相遇则必须满足下面条件，即相遇时次数满足 s = nr。即从起点之后下一次相遇需要循环 r 次。
2s - s = nr => s = nr
如下图所示，环长度r=4，则从起点后下一次相遇需要经过4次循环。
那么环的入口点怎么找呢？前面已经可知道第一次相遇要循环 r 次，而相遇时慢指针走的距离为 s=r，设链表总长度为L，链表头到环入口的距离为a，环入口到相遇点的距离为x，则L = a + r，可以推导出 a = (L-x-a)，其中L-x-a为相遇点到环入口点的距离，即链表头到环入口的距离a等于相遇点到环入口距离。
s = r = a + x => a + x = (L-a) => a = L-x-a
于是，在判断链表存在环后，从相遇点和头结点分别开始遍历，两个指针每次都走一步，当两个指针相等时，就是环的入口点。
/*** 查找链表中环入口*/
ListNode *findLoopNode(ListNode *head)
{ListNode *meetNode = listDetectLoop(head);if (!meetNode)return NULL;ListNode *headNode = head;while (meetNode != headNode) {meetNode = meetNode->next;headNode = headNode->next;}return meetNode;
}
3.6 链表模拟加法
题： 给定两个链表，每个链表的结点值为数字的各位上的数字，试求出两个链表所表示数字的和，并将结果以链表形式返回。假定两个链表分别为list1和list2，list1各个结点值分别为数字513的个位、十位和百位上的数字，同理list2的各个结点值为数字295的各位上的数字。则这两个数相加为808，所以输出按照从个位到百位顺序输出，返回的结果链表如下。
list1： (3 -> 1 -> 5 -> NULL)list2： (5 -> 9 -> 2 -> NULL)result： (8 -> 0 -> 8 -> NULL)
解： 这个题目比较有意思，需要对链表操作比较熟练。我们考虑两个数字相加过程，从低位到高位依次相加，如果有进位则标记进位标志，直到最高位才终止。设当前位的结点为current，则有：
current->data = list1->data + list2->data + carry
(其中carry为低位的进位，如果有进位为1，否则为0)
非递归代码如下：
/*** 链表模拟加法-非递归解法*/
ListNode *listEnumarateAdd(ListNode *list1, ListNode *list2)
{int carry = 0;ListNode *result = NULL;while (list1 || list2 || carry) {int value = carry;if (list1) {value += list1->value;list1 = list1->next;}if (list2) {value += list2->value;list2 = list2->next;}result = listAddNodeTail(result, value % 10);carry = ( value >= 10 ? 1: 0);}return result;
}
非递归实现如下：
/*** 链表模拟加法-递归解法*/
ListNode *listEnumarateAddRecursive(ListNode *list1, ListNode *list2, int carry)
{if (!list1 && !list2 && carry==0)return NULL;int value = carry;if (list1)value += list1->value;if (list2)value += list2->value;ListNode *next1 = list1 ? list1->next : NULL;ListNode *next2 = list2 ? list2->next : NULL;ListNode *more = listEnumarateAddRecursive(next1, next2, (value >= 10 ? 1 : 0));ListNode *result = listNewNode(carry);result->value = value % 10;result->next = more;return result;
}
3.7 有序单向循环链表插入结点
题： 已知一个有序的单向循环链表，插入一个结点，仍保持链表有序，如下图所示。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wc077RV6-1682156357973)(null)]
解： 在解决这个问题前，我们先看一个简化版本，就是在一个有序无循环的单向链表中插入结点，仍然保证其有序。这个问题的代码相信多数人都很熟悉，一般都是分两种情况考虑：
- 1）如果原来链表为空或者插入的结点值最小，则直接插入该结点并设置为头结点。
- 2）如果原来链表非空，则找到第一个大于该结点值的结点，并插入到该结点的前面。如果插入的结点值最大，则插入在尾部。
实现代码如下：
/*** 简化版-有序无循环链表插入结点*/
ListNode *sortedListAddNode(ListNode *head, int value)
{ListNode *node = listNewNode(value);if (!head || head->value >= value) { //情况1node->next = head;head = node;} else { //情况2ListNode *current = head;while (current->next != NULL && current->next->value < value)current = current->next;node->next = current->next;current->next = node;}return head;
}
当然这两种情况也可以一起处理，使用二级指针。如下：
/*** 简化版-有序无循环链表插入结点(两种情况一起处理)*/
void sortedListAddNodeUnify(ListNode **head, int value)
{ListNode *node = listNewNode(value);ListNode **current = head;while ((*current) && (*current)->value < value) {current = &((*current)->next);}node->next = *current;*current = node;
}
接下来看循环链表的情况，其实也就是需要考虑下面2点：
- 1） prev->value ≤ value ≤ current->value：
插入到prev和current之间。 - 2） value为最大值或者最小值：
插入到首尾交接处，如果是最小值重新设置head值。
代码如下：
/*** 有序循环链表插入结点*/
ListNode *sortedLoopListAddNode(ListNode *head, int value)
{ListNode *node = listNewNode(value);ListNode *current = head, *prev = NULL;do {prev = current;current = current->next;if (value >= prev->value && value <= current->value)break;} while (current != head);prev->next = node;node->next = current;if (current == head && value < current->value) // 判断是否要设置链表头head = node;return head;
}
3.8 输出链表倒数第K个结点
题： 给定一个简单的单向链表，输出链表的倒数第K个结点。
解1： 如果是顺数第K个结点，不用多思考，直接遍历即可。这个题目的新意在于它是要输出倒数第K个结点。一个直观的想法是，假定链表长度为L，则倒数第K个结点就是顺数的 L-K+1 个结点。如链表长度为3，倒数第2个，就是顺数的第2个结点。这样需要遍历链表2次，一次求长度，一次找结点。
/**
* 链表倒数第K个结点-遍历两次算法
*/
ListNode *getLastKthNodeTwice(ListNode *head, int k)
{int len = listLength(head); if (k > len)return NULL;ListNode *current = head; int i;for (i = 0; i < len-k; i++) //遍历链表，找出第N-K+1个结点current = current->next;return current;
}
解2： 当然更好的一种方法是遍历一次，设置两个指针p1,p2，首先p1和p2都指向head，然后p2向前走k步，这样p1和p2之间就间隔k个节点。最后p1和p2同时向前移动，p2走到链表末尾的时候p1刚好指向倒数第K个结点。代码如下：
/**
* 链表倒数第K个结点-遍历一次算法
*/
ListNode *getLastKthNodeOnce(ListNode *head, int k)
{ListNode *p1, *p2;p1 = p2 = head;for(; k > 0; k--) {if (!p2) // 链表长度不够Kreturn NULL;p2 = p2->next;}while (p2) {p1 = p1->next;p2 = p2->next;}return p1;
}