一、合并两个有序链表
题目来源：牛客网。
题目难度：简单。
题目描述：输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 <= n <= 1000,-1000≤节点值≤1000，要求：空间复杂度 O(1)，时间复杂度 O(n）。
题解关键思路：
- 定义一个哨兵位，易方便操作；
- 定义一个尾节点，插入时时刻改变尾节点，方便书写代码；
- 比较数据大小，依次尾插即可；
- 当有一个链表提前比较插入结束，不要忘记把另一个链表剩下的元素连接起来。
解题代码
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) { if(pHead1==NULL) { return pHead2; } if(pHead2==NULL) { return pHead1; } struct ListNode* head,* tail; head=tail=(struct ListNode*)malloc(sizeof(struct ListNode)); while(pHead1&&pHead2) { if(pHead1->val<pHead2->val) { tail->next=pHead1; tail=pHead1; pHead1=pHead1->next; } else { tail->next=pHead2; tail=pHead2; pHead2=pHead2->next; } } if(pHead1) { tail->next=pHead1; } if(pHead2) { tail->next=pHead2; } struct ListNode* plist=head->next; free(head); return plist; }
二、反转链表
题目来源：牛客网。
题目难度：简单。
题目描述：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度O(n) 。
题解关键思路：
- 反转next的指向即可；
- 定义三个节点，分别指向空、首节点、第二个节点，从首节点开始反转，依次向后访问。
- 也可考虑头插的思路，即定义一个新节点为空，把题目中的链表依次头插入新节点即可。
解题代码
// struct ListNode* ReverseList(struct ListNode* pHead ) { // if (pHead == NULL) // return NULL; // struct ListNode* n1, *n2, *n3; // n1 = NULL; // n2 = pHead; // n3 = pHead->next; // while (n2) { // n2->next = n1; // n1 = n2; // n2 = n3; // if (n3) // n3 = n3->next; // } // return n1; // } struct ListNode* ReverseList(struct ListNode* pHead ) { if(pHead==NULL) return NULL; struct ListNode* newhead=NULL; struct ListNode* cur=pHead; struct ListNode* next=cur->next; while(cur) { cur->next=newhead; newhead=cur; cur=next; next=cur->next; } return newhead; }
三、分割链表
题目来源：LeetCode。
题目难度：中等。
题目描述：给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。
题解关键思路：
- 定义两个新节点，把大于x的和小于x的分成两部分；
- 最后连接两部分；
- 注意，最后应该将最后一个节点的next置空，防止成回链。
解题代码
struct ListNode* partition(struct ListNode* head, int x) { struct ListNode* lesshead,*lesstail; lesshead=lesstail=(struct ListNode*) malloc(sizeof(struct ListNode)); lesstail->next=NULL; struct ListNode* greaterhead,*greatertail; greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode)); greatertail->next=NULL; struct ListNode* cur=head; while(cur) { if(cur->val<x) { lesstail->next=cur; lesstail=cur; } else { greatertail->next=cur; greatertail=cur; } cur=cur->next; } lesstail->next=greaterhead->next; greatertail->next=NULL; struct ListNode* plist=lesshead->next; free(lesshead); free(greaterhead); return plist; }
四、链表的回文结构
题目来源：LeetCode。
题目难度：简单。
题目描述：给定一个链表的 头节点
head，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
题解关键思路：
- 第一步：找到前半部分尾结点(快慢指针)；
- 第二步：翻转后半部分(翻转链表)；
- 第三步：判断是否是回文链表(判断前后两部分的节点是否一致)；
- 第四步：返回结果。
解题代码
struct ListNode* Reverse(struct ListNode* head) { struct ListNode* head1=head; struct ListNode *n1,*n2,*n3; n1=NULL; n2=head1; n3=head1->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; } bool isPalindrome(struct ListNode* head) { if(head==NULL||head->next==NULL) { return true; } struct ListNode* slow,*fast; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } struct ListNode*headRev=Reverse(slow); struct ListNode*headBef=head; while(headBef&&headRev) { if(headBef->val!=headRev->val) { return false; } else { headBef=headBef->next; headRev=headRev->next; } } return true; }
五、链表相交
题目来源：LeetCode。
题目难度：简单。
题目描述：给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
题解关键思路：
指针 curA 指向 A 链表，指针 curB 指向 B 链表，依次往后遍历；
先判断curA 和curB的尾是否相同，如果相同，则交叉，如果不同，则不交叉；
统计两个链表的节点数来判断谁长谁短；
从头遍历，比较长的链表指针先走两者之差，长度差就消除了如此，再依次同时往后遍历找相同即可。题解关键思路：
指针 curA 指向 A 链表，指针 curB 指向 B 链表，依次往后遍历；
先判断curA 和curB的尾是否相同，如果相同，则交叉，如果不同，则不交叉；
统计两个链表的节点数来判断谁长谁短；
从头遍历，比较长的链表指针先走两者之差，长度差就消除了如此，再依次同时往后遍历找相同即可。
解题代码
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA=headA; struct ListNode* curB=headB; int countA=1; int countB=1; while(curA->next||curB->next) { if(curA->next) { curA=curA->next; countA++; } if(curB->next) { curB=curB->next; countB++; } } if(curA!=curB) { return NULL; } int gap=abs(countA-countB); struct ListNode* longlist=headA; struct ListNode* shortlist=headB; if(countA<countB) { longlist=headB; shortlist=headA; } while(gap--) { longlist=longlist->next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist; }
六、环形链表
题目来源：LeetCode。
题目难度：中等。
题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
题解关键思路：
- 先判断是否为环形链表（快慢指针）；
- 是环形链表后，找入环点；
- 找入环点的方法：一个指针从相遇点开始，另个一指针从头开始，当两个指针相等时即为入环点。
解题代码
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow=head,*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { struct ListNode *meet=fast; while(meet!=head) { meet=meet->next; head=head->next; } return meet; } } return NULL; }
七、复制带有随机指针的链表
题目来源：LeetCode。
题目难度：中等。
题目描述：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点
题解关键思路：
- 首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，而后复制 random 指针。
- 最后我们把原链表和复制链表拆分出来，并将原链表复原即可。
解题代码
struct Node* copyRandomList(struct Node* head) { struct Node* cur=head; //插入相同的节点 while(cur) { struct Node* newnode=(struct Node*)malloc(sizeof(struct Node)); newnode->val=cur->val; //插入节点 newnode->next=cur->next; cur->next=newnode; cur=newnode->next; } //复制随机指针 cur=head; while(cur) { if(cur->random==NULL) { cur->next->random=NULL; } else { cur->next->random=cur->random->next; } cur=cur->next->next; } //拆解插入的指针 cur=head; struct Node* newhead=NULL,*newtail=NULL; while(cur) { struct Node*copy=cur->next; struct Node*next=copy->next; if(newtail==NULL) { newhead=newtail=copy; } else { newtail->next=copy; newtail=copy; } cur->next=next; cur=next; } return newhead; }
链表的常见OJ题我们先例举到这里，后续我们会持续更新的哦ovo~
感谢观看，希望本篇文章会对您有所帮助。
