字符串与链表刷题集（5.30-6.6）

1.字符串的两种写法

char* s = "hello"; char* s1[] = "hello";

前者被编译器放在文字常量区（只读数据段）

s只是一个指针，不能写：

s[0] = "a";

这是在修改只读内存，程序将直接出现段错误崩溃。

而数组形式的写法会让s1在栈或静态区拥有一份拷贝，这个副本就是可修改的。

2.找出字符串中第一个只出现一次的字符

int FirstUniqChar(char* str) { int count[256] = { 0 }; int sz = strlen(str); int i = 0; for (i = 0; i < sz; i++)//统计所有与元素出现的次数 { unsigned char ch = str[i]; count[ch]++;//字符的本质是ASCII，所以直接使用下标作为索引 } for (i = 0; i < sz; i++) { unsigned char ch = str[i];//注意索引仍需按照str的顺序来 if (count[ch] == 1) { return i; } } return -1; }

这是用数组模拟哈希表的写法，时间复杂度（n）。

重点在于，我们需要理解，字符本质是ASCII码值，也就是数字，所以它可以作为索引来记录自身出现的次数。

比如，a在某个字符串里出现了2次，那么我们创建遍历字符串后，count[97]这个位置就是2.

3.力扣题：两个链表模拟相加

2. 两数相加 - 力扣（LeetCode）

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { //建立哨兵位 struct ListNode dummy; dummy.next = NULL; //建立辅助指针tail，便于后续定位链表尾部 struct ListNode* tail = &dummy; //建立进位记录数carry int carry = 0; while (l1 || l2 || carry)//只要l1和l2有一个未到末尾，则仍需进行相加操作，同时carry若不为零，说明有进位需要则仍需进行相加操作 { int sum = carry;//用sum继承上一位的进位数 //对应位相加 if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } carry = sum / 10;//记录进位数 sum %= 10;//记录本次相加结果 //建立新节点 struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = sum; node->next = NULL; //将tail移动至尾部以此链接新节点 tail->next = node; tail = node; } return dummy.next;//用哨兵位访问链表首部并返回 }

本题真正的难点在于如何在链表中实现整数相加过程中进位的继承，以及对于单次计算结果，我们如何将其和过去的结果进行连接，最后就是使用哨兵位对情况的处理进行统一化。

显然，这需要对取模和除法运算以及链表实现的相关算法有一定理解，其中对变量carry和sum的处理尤为巧妙。

详情看注释。

4.力扣题：反转链表

https://leetcode.cn/problems/reverse-linked-list

题目要求我们反转一个没有前驱的单链表，实际上就是在考验我们头插相关的操作。

我们只需从头遍历链表，把每一个元素头插到新链表即可完成反转操作。

当然这里最好设立一个临时的哨兵节点以同一处理空链表的情况，具体代码如下：

typedef struct ListNode list; struct ListNode* reverseList(struct ListNode* head) { list* pcur1 = head; list dummy; dummy.next = NULL; list* guard = &dummy; while (pcur1) { list* NewNode = pcur1; pcur1 = pcur1->next; NewNode->next = guard->next; guard->next = NewNode; } return guard->next; }

这里，我们先用一个结构体指针NewNode记录当前位置，再让pcur向后移动，这样做的好处是，即使pcur移动了，我们仍然可以访问它未移动时的后方节点。

之后的代码很好理解，让NewNode的后继指向头节点，也就是哨兵节点的下一个，之后再把哨兵节点重新移动到头部，即让它的后继指向NewNode。

5.力扣题：合并两个升序链表

21. 合并两个有序链表 - 力扣（LeetCode）

解决这个问题，比较容易理解的思路是，依次从两个链表中选择数据较小的节点，插入到新链表中，直到某个链表来到尾部，再将另一个剩下的所有节点按原顺序插入到新链表中即可完成合并。

这里解释一下后半句。

由于两个链表是升序的，按照我们的取法——每次取二者较小的那个节点——只要一个链表来到末尾，那么另一个链表剩下的所有节点必然大于新链表的所有节点，所以直接按原顺序插入即可。

具体代码如下：

list* mergeTwoLists(list* head1, list* head2) { assert(head1 && head2); list dummy; dummy.next = NULL; list* tail = &dummy; list* cur1 = head1; list* cur2 = head2; while (cur1 && cur2) { if (cur1->x <= cur2->x) { tail->next = cur1; cur1 = cur1->next; } else { tail->next = cur2; cur2 = cur2->next; } tail = tail->next; } if (cur1) { tail->next = cur1; } else { tail->next = cur2; } return dummy.next; }

这里我们创建了一个tail来维护新链表的尾部，每当完成一次插入，tail就向后移动一位，直到cur1或者cur2来到尾部。

6.力扣题：寻找交叉节点

160. 相交链表 - 力扣（LeetCode）

这里先考虑简单的思路。我们先依次遍历两个链表计算出二者长度，再相减计算差值k。之后再让两个指针遍历一边，但这次，我们让处于长链表的指针先走k步，这样当两个指针相遇时，必然是到达了交叉地点。

typedef struct ListNode list; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { list *cur1 = headA, *cur2 = headB; int lenA = 0, lenB = 0; while (cur1) { cur1 = cur1->next; lenA++; } cur1 = headA; while (cur2) { cur2 = cur2->next; lenB++; } cur2 = headB; int k = lenA - lenB; if (k >= 0) { while (k--) cur1 = cur1->next; } else { k = -k; while (k--) cur2 = cur2->next; } while (cur1 != cur2) { cur1 = cur1->next; cur2 = cur2->next; } return cur1; }

当然，更优雅的解决方案是使用快慢指针。

还是两个指针遍历两个链表，但当某一个指针来到末尾时，我们让它跳到另一个链表的头部继续走，这样由于两个指针走的路程是相等的，那么必然会在交叉点相遇，具体的代码实现如下：

typedef struct ListNode list; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { list *cur1 = headA, *cur2 = headB; while (cur1 != cur2) { cur1 = (cur1 == NULL) ? headB : cur1->next; cur2 = (cur2 == NULL) ? headA : cur2->next; } return cur1; }

7.力扣题：重排链表

LCR 026. 重排链表 - 力扣（LeetCode）

我们可以先试用快慢指针找到链表的中间节点，截取链表的后半部分，再使用刚刚实现过的反转方法，把后半段链表反转，再按题目要求的规则插入原链表，具体的代码如下：

typedef struct ListNode list; list* FindMin(list* head) { list* fast = head; list* slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } list* revertlist(list* head) { list dummy; dummy.next = NULL; list* guard = &dummy; list* pcur = head; while (pcur) { list* next = pcur->next; pcur->next = guard->next; guard->next = pcur; pcur = next; } return guard->next; } void reorderList(struct ListNode* head){ //寻找中间节点 list* mid = FindMin(head); list* newhead = mid->next; mid->next = NULL; //反转后半段链表 list* revert_listhead = revertlist(newhead); //按规则插入 list* pcur = head; list* rpcur = revert_listhead; while (rpcur) { list* next = pcur->next; list* rnext = rpcur->next; rpcur->next = next; pcur->next = rpcur; pcur = next; rpcur = rnext; } }

但是这样的方法显然不够优雅。

我们知道，需要插入的节点和其插入的位置在下标上是有关系的，比如，第n节点要插入到下标0的后方，而第n - 1节点要插入到下标1的后方，如果我们能按下标访问链表，那这个问题就非常简单了。

这里提供一种思路。

我们可以先试用一个结构体类型的数组记录每一个节点指针，让后用索引i，j来访问数组，从而访问节点进行插入操作，具体代码如下：

typedef struct ListNode list; void reorderList(struct ListNode* head){ list* arr[50000]; list* pcur1 = head; int n = 0; for (n = 0; pcur1 != NULL; n++, pcur1 = pcur1->next) { arr[n] = pcur1; } int i = 0, j = 0; for (j = n - 1, i = 0; j > n / 2; j--, i++) { arr[j]->next = arr[i]->next; arr[i]->next = arr[j]; } arr[j]->next = NULL; }

这里一定需要注意n在走完第一个循环后变成了节点的总个数，所以j一定要从n - 1开始访问，否则就会越界。

再一个就是最后一定要将链表末尾next置空，否则链表就会变成循环。

8.力扣题：无重复的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

在数据不大时，这道题可以使用暴力解法。

int lenthIfUniquel(char* s, int t)//判断传入的区间是否有重复元素 { int len = t + 1; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { if (s[i] == s[j]) return 1;//由于最少传入长度为1，故返回1 } } return len; } int lengthOfLongestSubstring(char* s) { char* start = s; int sz = strlen(s); if (sz == 1) return 1; int tmpsz = 1;//start最多向后访问多少个字符 int len = 0; while (*start) { int tmp = 0, tmpsz = 1; while (tmpsz <= sz - 1) { tmp = lenthIfUniquel(start, tmpsz); if (len < tmp)//更新最大长度 len = tmp; tmpsz++;//铆钉左边界后，不断扩展右边界 } start++; sz--; } return len; }

从字符串头部开始，依次选取区间，再判断这个区间是否有重复字符，若有则返回1，若无则返回子串长度。每轮检查后，都不断更新最大长度，最终得到最大非重复子串。

但显然，这个暴力解法的时间复杂度来到了惊人的N^3,肯定通过不了所有测试用例。

本题最高效的解法是使用哈希表，但为了照顾还未学习哈希表的同学，我们用更加简单易懂的方式来解决。

在第二道题中，我们已经知道一种思路：字符本质上是数字，因此可以使用数组来记录它出现的次数，我们可以把这个思路应用到这里：

以索引 i 作为左边界，j 作为右边界，i作为第一层循环，从字符串头部遍历，j 作为内层循环从 i开始遍历。创建一个数组seen，把遍历过的字符作为下标将1存入数组，表示这个字符在区间i - j已经存在。

如果访问到数组seen里某一个下标下的元素是1，就意味着重复，就跳出内层循环，让i++，即右移左边界，继续检查，如果未检查到重复，就利用j 和 i不断更新当前字符串长度。

代码如下：

int lengthOfLongestSubstring(char* s) { int i = 0, j = 0; int sz = strlen(s); int max_len = 0; for (i = 0; i < sz; i++) { int seen[5000] = { 0 }; for (j = i; j < sz; j++) { if (seen[(unsigned char)s[j]]) break; seen[(unsigned char)s[j]] = 1; max_len = MAX(max_len, j - i + 1); } } return max_len; }