数据结构与算法——链表OJ十大面试题，看懂直接解决链表问题

目录

一：移除链表元素

二：反转链表

三：链表的中间结点

四：返回倒数第k个结点

五：合并两个有序链表

六：链表分割

七：链表的回文结构

八：相交链表

九：环形链表I

十：环形链表II

十一：随机链表的复制

十二：对链表进行插入排序

十三：删除链表中重复的结点

---

目录

一：移除链表元素

二：反转链表

三：链表的中间结点

四：返回倒数第k个结点

五：合并两个有序链表

六：链表分割

七：链表的回文结构

八：相交链表

九：环形链表I

十：环形链表II

十一：随机链表的复制

---

一：移除链表元素

题型链接：203. 移除链表元素 - 力扣（LeetCode）

题目要求：删除链表中等于给定值 val 的所有节点

 解题思路：

1.遇空则返回空。

2.需要两个指针来解决。一个指针判断是否等于val，另一个指针用来正确链表的返回。

 解答步骤：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {if(head==NULL){return NULL;}struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));phead->next = head;head = phead;struct ListNode* prev = phead;struct ListNode* tail = prev->next;while(tail){while(tail && tail->val == val){prev->next = tail->next;free(tail);tail = prev->next;}while(tail && tail->val != val){tail = tail->next;prev =prev->next;}}struct ListNode* ret = phead->next;free(phead);return ret;
}

二：反转链表

题型链接：206. 反转链表 - 力扣（LeetCode）

题目要求：反转一个单链表

解题思路：

1.遇空则返回空。

2.需要使用三个指针来解决。两个指针用来反转，一个指针用来标记位置。

解答步骤：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL){return head;}struct ListNode* curprev = NULL;struct ListNode* cur = head;struct ListNode* curnext = cur->next;while(cur){cur->next = curprev;curprev = cur;cur = curnext;if(cur)curnext = curnext->next;}return curprev;}

三：链表的中间结点

题型链接：876. 链表的中间结点 - 力扣（LeetCode）

题目要求：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点

解题思路：

1.遇空则返回空。

2.需要使用到两个指针（快慢指针），一个指针一次走一步，另一个指针一次走两步。

解答步骤：

struct ListNode* middleNode(struct ListNode* head) {if(head==NULL){return NULL;}struct ListNode* cur = head;struct ListNode* cur_2 = head;while(cur_2 && cur_2->next){cur = cur->next;cur_2 = cur_2->next->next;}return cur;
}

四：返回倒数第k个结点

题型链接：面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

题目要求：输入一个链表，输出该链表中倒数第k个结点

解题思路：

需要使用两个指针，一个指针先走k步，然后两个指针再同时走，直至快指针为NULL。

解题步骤：

int kthToLast(struct ListNode* head, int k){struct ListNode* fast = head;struct ListNode* slow = head;while(k--){fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}return slow->val;    }

五：合并两个有序链表

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

题目要求：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

解题思路：

1.先做一个头节点

2.通过L1和L2指针的比较依次将其连接到新头节点的后面。

解题步骤：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = phead;struct ListNode* l1 = list1;struct ListNode* l2 = list2;while(l1 && l2){if(l1->val < l2->val){cur->next = l1;cur = l1;l1 = l1->next;}else{cur->next = l2;cur = l2;l2 = l2->next;}}if(l1)cur->next = l1;elsecur->next = l2;return phead->next;
}

六：链表分割

题型链接：链表分割_牛客题霸_牛客网 (nowcoder.com)

题目要求：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

解题步骤：

ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* newnode1 = (ListNode*)malloc(sizeof(ListNode));ListNode* newnode2 = (ListNode*)malloc(sizeof(ListNode));ListNode* list1 = newnode1;ListNode* list2 = newnode2;ListNode* ls1 = newnode1;ListNode* ls2 = newnode2;ListNode* tail = pHead,*next = pHead->next;while(tail){if(tail->val<x){ls1->next = tail;ls1 = tail;ls1->next = NULL;}else {ls2->next = tail;ls2 = tail;ls2->next = NULL;}tail = next;if(tail)next = next->next;}ls1->next = newnode2->next;list1 = newnode1->next;free(newnode1);free(newnode2);return list1;}

七：链表的回文结构

题型链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

题目要求：链表的回文结构。

解题步骤：

ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* newnode1 = (ListNode*)malloc(sizeof(ListNode));ListNode* newnode2 = (ListNode*)malloc(sizeof(ListNode));ListNode* list1 = newnode1;ListNode* list2 = newnode2;ListNode* ls1 = newnode1;ListNode* ls2 = newnode2;ListNode* tail = pHead,*next = pHead->next;while(tail){if(tail->val<x){ls1->next = tail;ls1 = tail;ls1->next = NULL;}else {ls2->next = tail;ls2 = tail;ls2->next = NULL;}tail = next;if(tail)next = next->next;}ls1->next = newnode2->next;list1 = newnode1->next;free(newnode1);free(newnode2);return list1;}

八：相交链表

题型链接：160. 相交链表 - 力扣（LeetCode）

题目要求：输入两个链表，找出它们的第一个公共结点

解题步骤：

truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int ha = 0;int hb = 0;struct ListNode* cura = headA;struct ListNode* curb = headB;while(cura){ha++;cura = cura->next;}while(curb){hb++;curb = curb->next;}cura = headA;curb = headB;struct ListNode* long1 = headA;struct ListNode* short1 = headB;if(ha<hb){long1= headB;short1 = headA;}int i = fabs(ha-hb);while(i){long1 = long1->next;i--;}while(long1!=short1){long1 = long1->next;short1 = short1->next;}if(long1==NULL)return NULL;return long1;
}

九：环形链表I

题型链接：141. 环形链表 - 力扣（LeetCode）

题目要求：给定一个链表，判断链表中是否有环

解题步骤：

bool hasCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast!=NULL&&fast->next!=NULL){slow = slow->next;fast = fast->next->next;if(slow==fast)return true;}return false;
}

十：环形链表II

题型链接：142. 环形链表 II - 力扣（LeetCode）

题目要求：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

解题步骤：

struct ListNode *getIntersectionNode(struct ListNode **headA, struct ListNode **headB) {int ha = 0;int hb = 0;struct ListNode* cura = *headA;struct ListNode* curb = *headB;while(cura){ha++;cura = cura->next;}while(curb){hb++;curb = curb->next;}cura = *headA;curb = *headB;struct ListNode* long1 = *headA;struct ListNode* short1 = *headB;if(ha<hb){long1= *headB;short1 = *headA;}int i = fabs(ha-hb);while(i){long1 = long1->next;i--;}while(long1!=short1){long1 = long1->next;short1 = short1->next;}if(long1==NULL)return NULL;return long1;
}

十一：随机链表的复制

题型链接：138. 随机链表的复制 - 力扣（LeetCode）

题目要求：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝

解题步骤：

struct Node* copyRandomList(struct Node* head) {// 1.拷贝节点到源节点的后面struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;struct Node* next = cur->next;cur->next = copy;copy->next = next;cur = next;}// 2.控制拷贝节点的 randomcur = head;while(cur){struct Node* copy = cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random = cur->random->next;}cur = copy->next;}// 连接新链表 and 恢复原链表cur = head;struct Node* copyhead = NULL,*copytail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;// 连接新链表if(copyhead==NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}// 恢复原链表cur->next = next;cur = next;}return copyhead;
}