文章目录
题目
203.移除链表元素
这个题目有两种方法，第一种是创建新的链表，然后将原链表遍历一遍，跳过所有值为val的节点，将所有值不为val的节点移动到新链表里，并返回新链表的头节点。第二种是直接遍历链表逐个删除目标节点。
方法一：创建新链表
/*struct ListNode {
int val;
struct ListNode *next;
}; */
typedef struct ListNode ListNode; // 为结构体定义一个别名，方便后续使用
// 函数声明：删除链表中所有值等于val的节点，并返回新的头节点
struct ListNode* removeElements(struct ListNode* head, int val) {
if(head==NULL) // 如果链表为空，则直接返回
return head;
ListNode* newhead, *newtail; // 定义新的头节点和尾节点指针
newhead = newtail = NULL; // 初始化新的头尾节点为NULL
ListNode* pcur = head; // 定义一个指针，用于遍历原始链表
while(pcur) { // 遍历原始链表
if(pcur->val != val) { // 如果当前节点的值不等于给定的val
if(newhead == NULL) { // 如果新的链表还未初始化
newtail = newhead = pcur; // 则将当前节点设为新的头节点和尾节点
} else { // 如果新的链表已经初始化
newtail->next = pcur; // 将当前节点添加到新的链表的尾部
newtail = newtail->next; // 更新尾节点指针
}
}
pcur = pcur->next; // 移动到原始链表的下一个节点
}
/*while循环完成之后,如果要删除的节点是原链表的最后一个，
由于此时newtail是原链表的倒数第二个，所以它虽然是新链表的最后一个，
但是它还是指向了那个需要被删除的结点，所以这里需要将newtail->next=NULL;
但是不能直接写newtail->next=NULL;在这之前需要判断这个新链表是否为空，
如果为空这个语句就是错误的。新链表为空的情况就是链表数据都是一样的
而且这个数据刚好是要删除的数据。*/
if(newhead != NULL) { // 如果新的链表不为空
newtail->next = NULL; // 确保新的链表的尾节点指向NULL，防止形成环形链表
}
return newhead; // 返回新的头节点
}
方法二：直接遍历链表
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为链表节点结构体定义别名，方便后续使用
typedef struct ListNode ListNode;
// 函数声明：删除链表中所有值等于val的节点，并返回新的头节点
struct ListNode* removeElements(struct ListNode* head, int val) {
// 如果链表为空，则直接返回空指针
if(head == NULL)
return head;
ListNode *pcur = head; // 当前节点指针，用于遍历链表
ListNode *prev = NULL; // 前一个节点指针，用于删除操作
// 遍历链表
while(pcur) {
// 如果当前节点的值等于给定的val
if(pcur->val == val) {
// 如果当前节点是头节点且需要被删除
if(prev == NULL) {
head = head->next; // 更新头节点为下一个节点
pcur = head; // 更新当前节点为新的头节点
} else {
prev->next = pcur->next; // 将前一个节点的next指针指向当前节点的下一个节点，从而跳过当前节点
free(pcur); // 释放当前节点的内存
pcur = prev->next; // 更新当前节点为下一个节点
}
} else {
prev = pcur; // 更新前一个节点为当前节点
pcur = pcur->next; // 更新当前节点为下一个节点
}
}
return head; // 返回新的头节点指针
}
876.链表的中间结点
方法：这个题目的解法是快慢指针法，即创建两个指针，快指针fast每次移动两个节点，慢指针slow每次移动一个节点，因此当fast遍历完整个链表时，slow刚好遍历到链表的一半，( 当该链表的结点为偶数个时fast为空，当该链表的结点为奇数个时fast->next为空，)从而实现了找到链表中间节点的目的。
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为结构体定义别名，方便后续使用
typedef struct ListNode ListNode;
// 函数用于找到链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {
// 如果链表为空，则直接返回NULL
if(head==NULL){
return head;
}
// 定义两个指针，fast和slow，都初始化为头节点
ListNode* fast, *slow;
fast = slow = head;
// 当fast指针和fast的下一个节点都不为空时，执行循环
// 这里使用了快慢指针的技巧：slow每次移动一步，而fast每次移动两步
// 当fast到达链表尾部时，slow刚好到达链表的中间位置
while(fast != NULL && fast->next != NULL){
slow = slow->next; // slow指针每次移动一个节点
fast = fast->next->next; // fast指针每次移动两个节点
}
// 返回中间节点，由于fast的移动速度是slow的两倍，
// 当fast到达链表尾部时，slow刚好指向链表的中间节点
return slow;
}
024.反转链表
题目链接
方法一：通过迭代地改变节点间的连接关系，实现了链表的反转。在每次迭代中，它将当前节点的 next 指针指向前一个节点，然后更新头节点为当前节点，并移动到下一个节点继续处理，直到所有节点都处理完毕。最后，返回新链表的头节点。这个题目先画图自己理解一遍效果更好。
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为结构体 ListNode 创建一个别名，方便后续使用
typedef struct ListNode ListNode;
// 反转链表的函数
struct ListNode* reverseList(struct ListNode* head) {
// 如果头节点为空，则直接返回，因为没有节点需要反转
if(head==NULL){
return head;
}
// 初始化一个指针 pcur，指向原链表的第二个节点（即头节点的下一个节点）
// 这一步相当于“断开头结点”，使原链表的头节点成为新链表的尾节点
ListNode* pcur = head->next;
// 将原链表的头节点的 next 指针设为 NULL，使其成为新链表的尾节点
head->next = NULL;
// 当 pcur 不为空时，即原链表中还有节点未处理时，继续循环
while(pcur){
// 记录 pcur 的下一个节点，以便后续处理
ListNode* next = pcur->next;
// 将 pcur 的 next 指针指向前一个节点，实现反转
pcur->next = head;
// 更新头节点为当前节点，因为当前节点已经成为了新链表的头节点
head = pcur;
// 移动 pcur 到下一个待处理的节点
pcur = next;
}
// 当所有节点都处理完毕后，head 指针将指向新链表的头节点
// 返回新链表的头节点
return head;
}
方法二：
这个方法与前一个方法原理一样，不同的是用了三个指针，通过迭代地改变每个节点的next指针来反转链表。它使用了三个指针变量：n1、n2和n3，分别表示反转后的前一个节点、当前节点和下一个节点。在每次循环中，它都会更新当前节点的next指针，使其指向前一个节点，然后移动指针以处理下一个节点。这个过程会一直持续到处理完所有的节点。最后，函数返回新的头节点，即原链表的尾节点。这个也要先画图自己理解一遍效果更好。
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为结构体定义别名，便于后续使用
typedef struct ListNode ListNode;
// 反转链表的函数
struct ListNode* reverseList(struct ListNode* head) {
// 如果链表为空，则直接返回
if(head == NULL) {
return head;
}
// 初始化三个指针，分别代表反转后的链表的前一个节点、当前节点和后一个节点
ListNode* n1 = NULL; // 反转后的前一个节点，初始为NULL
ListNode* n2 = head; // 当前处理的节点，初始为头节点
ListNode* n3 = head->next; // 当前处理节点的下一个节点
// 当当前节点不为空时，进行循环
while(n2) {
// 将当前节点的next指针指向前一个节点，实现反转
n2->next = n1;
// 更新前一个节点为当前节点
n1 = n2;
// 将当前节点更新为下一个节点
n2 = n3;
// 如果下一个节点不为空，则更新下一个节点为其后续的节点
if(n3 != NULL) {
n3 = n3->next;
}
}
// 当循环结束时，n1会指向新的头节点，返回它
return n1;
}
21.合并两个有序链表
题目链接
方法：通过比较两个链表节点的值，按照升序将节点连接到新的链表上。最后，返回新链表的头节点。
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为ListNode结构体定义一个别名，方便后续使用
typedef struct ListNode ListNode;
// 合并两个升序链表的函数
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 如果两个链表都为空，则直接返回NULL
if(list1 == NULL && list2 == NULL) {
return NULL;
}
// 如果第一个链表为空，则直接返回第二个链表
if(list1 == NULL) {
return list2;
}
// 如果第二个链表为空，则直接返回第一个链表
if(list2 == NULL) {
return list1;
}
// 定义新的链表头和尾指针，初始化为NULL
ListNode *newhead, *newtail;
newhead = newtail = NULL;
// 定义两个指针分别遍历两个链表
ListNode *n1 = list1;
ListNode *n2 = list2;
// 当两个链表都不为空时，进行循环
while(n1 && n2) {
// 如果第一个链表的当前节点值小于第二个链表的当前节点值
if(n1->val < n2->val) {
// 如果新链表为空，则将新链表的头和尾都指向第一个链表的当前节点
if(newhead == NULL) {
newhead = newtail = n1;
} else {
// 否则，将新链表的尾节点的next指向第一个链表的当前节点，并更新尾节点
newtail->next = n1;
newtail = newtail->next;
}
// 移动第一个链表的指针
n1 = n1->next;
} else {
// 类似地处理第二个链表的节点
if(newhead == NULL) {
newhead = newtail = n2;
} else {
newtail->next = n2;
newtail = newtail->next;
}
n2 = n2->next;
}
}
// 如果第一个链表还有剩余节点，则将其连接到新链表的尾部
if(n1 != NULL) {
newtail->next = n1;
}
// 如果第二个链表还有剩余节点，则将其连接到新链表的尾部
if(n2 != NULL) {
newtail->next = n2;
}
// 返回新链表的头节点
return newhead;
}
面试题02.04分割链表
题目链接
方法一：通过创建两个新的链表来分别存储小于x和大于等于x的节点，并在最后将它们连接起来。注意，在连接两个链表时，需要确保小于x的链表尾部指向大于等于x的链表头部，并且大于等于x的链表尾部指向NULL。
/*
struct ListNode {
int val;
struct ListNode *next;
}; */
typedef struct ListNode ListNode;
// partition函数，输入链表头节点head和特定值x，返回分隔后的链表头节点
struct ListNode* partition(struct ListNode* head, int x) {
// 如果链表为空，则直接返回NULL
if(head == NULL)
return head;
// 定义两个新链表的头尾指针，一个用于存放小于x的节点，另一个用于存放大于等于x的节点
ListNode *head1 = NULL; // 小于x的链表头节点
ListNode *tail1 = NULL; // 小于x的链表尾节点
ListNode *head2 = NULL; // 大于等于x的链表头节点
ListNode *tail2 = NULL; // 大于等于x的链表尾节点
// 定义一个指针用于遍历原链表
ListNode *pcur = head;
// 遍历原链表，根据节点值的大小分配到两个新链表中
while(pcur) {
if(pcur->val < x) {
// 如果小于x的链表为空，则将当前节点设置为头尾节点
if(head1 == NULL) {
head1 = tail1 = pcur;
} else {
// 否则，将当前节点添加到小于x的链表尾部
tail1->next = pcur;
tail1 = tail1->next;
}
} else {
// 如果大于等于x的链表为空，则将当前节点设置为头尾节点
if(head2 == NULL) {
head2 = tail2 = pcur;
} else {
// 否则，将当前节点添加到大于等于x的链表尾部
tail2->next = pcur;
tail2 = tail2->next;
}
}
// 移动到原链表的下一个节点
pcur = pcur->next;
}
// 处理两个新链表的连接和尾节点
if(tail1) { //这里要考虑tail1是否为空
tail1->next = head2; // 将大于等于x的链表连接到小于x的链表尾部
} else {
head1 = head2; // 如果小于x的链表为空，则直接返回大于等于x的链表
}
if(tail2) { //这里要考虑tail2是否为空
tail2->next = NULL; // 确保大于等于x的链表尾部指向NULL
}
return head1; // 返回分隔后的链表头节点
}
方法二：这个方法跟之前的差别主要是省去了判断新的大小链表的头节点是否为空的情况。首先创建两个新的链表，一个用于存储小于 x 的节点（lesshead 和 lesstail），另一个用于存储大于或等于 x 的节点（graterhead 和 gratertail）。然后，它遍历原始链表，并根据节点的值将其添加到适当的新链表中。最后，它将两个新链表连接起来，并返回新链表的头节点。
/*struct ListNode {
int val;
struct ListNode *next;
}; */
#include<stdlib.h>
typedef struct ListNode ListNode;
// 分隔链表的函数
struct ListNode* partition(struct ListNode* head, int x) {
// 如果链表为空，则直接返回
if (head == NULL)
return head;
// 初始化小于x的链表
ListNode* lesshead, *lesstail;
lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode)); // 分配内存
lesstail->next = NULL; // 初始化新链表的尾节点
// 初始化大于或等于x的链表
ListNode* graterhead, *gratertail;
graterhead = gratertail = (ListNode*)malloc(sizeof(ListNode)); // 分配内存
gratertail->next = NULL; // 初始化新链表的尾节点
ListNode* pcur = head; // 用于遍历原始链表的指针
while (pcur) {
if (pcur->val < x) {
// 如果当前节点的值小于x，则添加到小于x的链表中
lesstail->next = pcur;
lesstail = lesstail->next;
} else {
// 否则，添加到大于或等于x的链表中
gratertail->next = pcur;
gratertail = gratertail->next;
}
pcur = pcur->next; // 移动到原始链表中的下一个节点
}
// 连接两个新链表，并确保大于或等于x的链表以NULL结尾，防止死循环
lesstail->next = graterhead->next; // 注意graterhead节点本身不包含实际值
gratertail->next = NULL; // 重要：防止死循环
// 释放临时头节点，并返回新链表的头节点（即小于x的链表的第一个实际节点）
ListNode* ret = lesshead->next; // 一定要在释放lesshead之前获取这个值
free(lesshead); // 释放小于x的链表的临时头节点
free(graterhead); // 释放大于或等于x的链表的临时头节点
return ret; // 返回新链表的头节点
}
面试题02.02.返回倒数第K个节点
题目链接
方法一：双指针法，当两个指针n1和n2在链表中移动，并且它们之间始终保持固定的距离k时，我们可以利用这个特性来定位特定位置的节点。n2先移动k步，从而在n1和n2之间创建了k个节点的间隔。随后，当两个指针以相同的速度（每次一步）沿链表向前移动时，它们之间的相对距离保持不变。这意味着，当n2指针到达链表尾部时，n1指针将恰好位于倒数第k个节点。
// 定义链表节点结构体
struct ListNode {
int val; // 节点的值
struct ListNode *next; // 指向下一个节点的指针
};
// 为结构体定义别名，方便后续使用
typedef struct ListNode ListNode;
// 函数用于找出单向链表中倒数第k个节点的值
int kthToLast(struct ListNode* head, int k) {
ListNode* n1, *n2; // 定义两个指针n1和n2
n1 = n2 = head; // 初始化时，两个指针都指向链表的头节点
// 先让n2指针向前移动k步
while (k--) {
n2 = n2->next;
}
// 当n2不为NULL时，同时移动n1和n2
// 当n2到达链表尾部时，n1就会停在倒数第k个节点上
while (n2) {
n1 = n1->next;
n2 = n2->next;
}
// 返回倒数第k个节点的值
return n1->val; // 注意这里返回的是节点的值，而不是节点本身
}
方法二：这个方法比较简单，就是直接算出头节点要走的步数就行了，具体步骤请看代码
/* struct ListNode {
int val;
struct ListNode *next;
}; */
// 为结构体定义别名，方便后续使用
typedef struct ListNode ListNode;
// 函数用于找出单向链表中倒数第k个节点的值
int kthToLast(struct ListNode* head, int k) {
ListNode* pcur = head; // 定义一个指针pcur，初始指向链表的头节点
int count = 0; // 用于记录链表的长度
// 遍历链表，计算链表的长度
while (pcur) {
pcur = pcur->next; // 移动指针到下一个节点
count++; // 链表长度加1
}
// 计算从链表头开始，需要前进多少个节点才能到达倒数第k个节点
int a = count - k;
// 再次遍历链表，前进到倒数第k个节点
while (a--) {
head = head->next; // 移动头指针
}
// 返回倒数第k个节点的值
return head->val;
}
023.相交链表
题目链接
方法一：这个方法首先计算了两个链表的长度，然后根据长度差调整了两个链表的起始比较位置，确保从同一位置开始比较。之后，它同时遍历两个链表，直到找到相交点或遍历完整个链表。
/*
struct ListNode {
int val;
struct ListNode *next;
}; */
// 为ListNode定义一个别名，便于后续使用
typedef struct ListNode ListNode;
// 函数w用于计算链表的长度
int w(ListNode* head) {
int count = 0; // 初始化计数器
ListNode *pcur = head; // 定义一个指针，从链表头开始遍历
// 遍历链表，计算节点数量
while (pcur) {
pcur = pcur->next;
count++;
}
return count; // 返回链表的长度
}
// 主函数，用于找到两个链表的相交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
// 如果任何一个链表为空，则直接返回NULL，因为没有相交的可能
if (headA == NULL || headB == NULL)
return NULL;
// 计算两个链表的长度
int lenA = w(headA);
int lenB = w(headB);
// 计算两个链表长度的差值
int offset = abs(lenA - lenB); //abs()函数用于计算绝对值
// 定义两个指针，分别指向两个链表
ListNode *plong = headA; // 较长的链表
ListNode *pshort = headB; // 较短的链表
// 根据链表长度，调整指针的起始位置，确保从相同的起点开始比较
if (lenB > lenA) {
plong = headB;
pshort = headA;
}
// 将长链表的指针向前移动offset个位置
while (offset--) {
plong = plong->next;
}
// 同时遍历两个链表，查找相交点
while (plong) {
if (plong == pshort) {
return plong; // 找到相交点，返回该节点
}
plong = plong->next;
pshort = pshort->next;
}
return NULL; // 没有找到相交点，返回NULL
}
方法二：这个方法的关键在于两个指针的“跳转”行为。当它们到达各自链表的末尾时，会跳转到另一个链表的头部继续遍历。这样，如果两个链表相交，那么它们最终会在相交点“相遇”。如果两个链表长度不同，这种“跳转”行为也能确保两个指针最终会相遇（要么在相交点，要么同时指向NULL）。注意这题不能直接用haedA和headB，否则会当headA走完了，要返回到headB的时候，headB已经走了很多步了，不是headB一开始的位置了。
/*
struct ListNode {
int val;
struct ListNode *next;
}; */
// 为ListNode定义一个别名，便于书写和理解
typedef struct ListNode ListNode;
// 主函数，用于找到两个链表的相交起始节点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 如果任何一个链表为空，则直接返回NULL，因为没有相交的可能
if(headA == NULL || headB == NULL)
return NULL;
// 定义两个指针，分别遍历两个链表
ListNode *pa = headA;
ListNode *pb = headB;
// 当两个指针不相等时，继续循环
while(pa != pb) {
// 如果pa到达链表A的末尾，则将其重新指向链表B的头节点
pa = pa == NULL ? headB : pa->next; //这个是三目运算符
// 如果pb到达链表B的末尾，则将其重新指向链表A的头节点
pb = pb == NULL ? headA : pb->next;
}
// 循环结束时，pa和pb要么都指向相交的起始节点，要么都为NULL（表示没有交点）
// 在这个算法中，如果两个链表长度不同，较长的链表指针会先到达链表尾部，
// 然后跳转到另一个链表的头部继续遍历，直到两个指针相遇。
// 如果两个链表相交，那么它们最终会在相交点相遇；
// 如果不相交，那么两个指针会同时指向NULL。
// 返回相交节点，或者在没有相交的情况下返回NULL
return pa;
}