💯💯💯链表经典面试题❗❗❗炒鸡经典，本篇带有图文解析，建议动手刷几遍。
🟥1.反转链表
方法一：利用双指针逆转方向
将各个结点的连接方向都倒过来，2结点指向1结点，3结点指向2结点等，我们只要将让每个结点的next指向前一个结点的地址
双指针–将指针指向前面，最后一个变成头。两个指针，一前一后
注意点：
- 单链表不能往前走
- 第一个指针首先指向NULL ，第二个指针在后面，这两个指针用来转变指向
不过这时第二个指针的后面的地址无法知道，这时需要第三个指针用来记录第二个指针后面的结点的地址。
- 当第三个指针往后走的时候可能为NULL，要注意下
代码如下：
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL)//如果链表为空则直接返回NULL return NULL; struct ListNode* prev = NULL;//与cur搭配，记录前面的，一开始为NULL struct ListNode* cur = head;//一开始为第一个结点，所以将head传给cur，让cur遍历链表 struct ListNode* next =cur->next;//next用来记录cur后面结点的地址 while (cur)//当cur不为NULL时进行 { //方向逆转 cur->next = prev;//将每一个结点的next指向前一个结点的地址 //迭代--让我们的条件往后执行 prev = cur;//让pre跑到cur的位置上来 cur = next;//让cur跑到next的位置上来 if (next)//这里next可能会跑着跑着为NULL了，所以需要判断下 next = next->next;//往后跑 } return prev;//最后尾就是头了，将尾传回去 }
方法2：利用头插原理
取原结点头插到新链表
原本是1 2 3 4 5
我们只要将每个结点拿下来，然后头插到一个新链表上就会变成5 4 3 2 1了
代码如下：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head;//利用cur进行遍历，不要用形参head struct ListNode* newnode = NULL;//首先创建一个新的空链表 while (cur)//当cur为空时结束 { //首先要记录下来cur后面结点的地址 struct ListNode* next = cur->next; //头插 cur->next = newnode;//将取下来的结点头插到新链表中 newnode = cur;//更新头指针 cur = next;//cur要往后走 } return newnode;//返回新链表的头指针 }
🟧2.合并两个有序链表
这种题目在数组中也有类似的，原理也是一样，合并两个有序数组
也就是依次比较取小的结点尾插，最后如果比较完还有结点直接尾插到没有结点的后面去。
注意点：
- 当第一次尾插到一个新链表时，我们需要的 是进行直接赋值，将第一个结点直接赋值给新链表的头指针而不能进行尾插
- 当第一次以后才可以进行真正的尾插
- 当其中有一个或两个链表为空链表的话，那么直接跳过比较环节，而进入将还有结点的直接尾插到没有结点的后面去
这时因为没有结点的链表为NULL，所以就无法访问它的next也就无法将它和另一个链表链接起来。
所以这时我们需要在前面讨论一下，当其中有一个链表为NULL，则直接返回另外一个链表。
方法1：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ if (list1 == NULL)//当链表1为空则直接返回链表2 return list2; if (list2 == NULL)//当链表2为空则直接返回链表1 return list1; struct ListNode* cur1 = list1, * cur2 = list2;//利用cur1，cur2遍历链表 struct ListNode* head = NULL, * tail = NULL;//head,用来传回，tail用来找尾 while (cur1 && cur2)//当其中有一个结束就结束 { if (cur1->val < cur2->val)//哪个小就尾插谁 { //将小的尾插 //但一开始为空第一步就是赋值 if (head == NULL) { head = tail = cur1; } //接下来才是真正的尾插 else { tail->next = cur1;//将cur1链接在tail的后面 tail = tail->next;//tail要往后找尾，这样就不需要每次从开始进行找尾了 } cur1 = cur1->next;//cur往后走 } else { //将小的尾插 //但一开始为空第一步就是赋值 if (head == NULL) { head = tail = cur2; } //接下来才是真正的尾插 else { tail->next = cur2; tail = tail->next; } cur2 = cur2->next; } } //将长的链表指针尾插到tail后面 //不过还有一种情况就是plist为空cur1为空，则tail还是NULL，这种情况需要讨论 if (cur1) { tail->next = cur1; } else { tail->next = cur2; } return head;//返回head }
还有一种方法可以避免讨论tail的next是否为空，和第一次尾插需要赋值等问题。
我们可以利用带有头哨兵卫的头结点。
这样tail永远不可能为空了，就不需要讨论那么多为空的情况了。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* cur1 = list1, * cur2 = list2; struct ListNode* head =NULL,* tail = NULL; struct ListNode* guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//动态开辟一个哨兵头结点，让tail一开始就指向头结点，这样tail就永远不会为NULL了 while (cur1 && cur2)//当其中有i一个结束就结束 { if (cur1->val < cur2->val) { //将小的尾插 //不需要进行讨论第一个头节点为NULL的情况了，直接进行尾插 tail->next = cur1; tail = tail->next; cur1 = cur1->next; } else { //将小的尾插 tail->next = cur2; tail = tail->next; cur2 = cur2->next; } } //将长的链表指针尾插到tail后面 //如果没有哨兵头，plist为空cur1为空，则tail还是NULL，这种情况就需要讨论 //但先走有了哨兵头结点，tail不可能为空，直接让tail的next与另一个链表剩余的结点链接起来 if (cur1) { tail->next = cur1; } else { tail->next = cur2; } head=guard->next;//将第一个结点的地址记录下来 free(guard);//释放guard return head; }
🟨3.链表分割
要求将所有小于x的结点排在其他结点之前，且不能改变原来的数据顺序
我们可以这样做：
- 将小于x的结点插入到一个链表中
- 将大于x的结点插入到一个链表中
- 最后将两个链表链接起来。
不过这里我们最好使用带有哨兵头的链表，这样可以减少进行对NULL的讨论不然会很麻烦
比如如果数据全是 6 6 6 6 6 而x为5
则less链表为空，那么将两个链表链接起来有会出问题，ltail都为NULL还有next吗？，所以我们使用带有哨兵卫的链表能很好的减少这种讨论。
class Partition { public: ListNode* partition(ListNode* pHead, int x) { ListNode* Lguard,*Gguard,*ltail,*gtail; Lguard=ltail=(ListNode*)malloc(sizeof(ListNode));//less链表的哨兵头 Gguard=gtail=(ListNode*)malloc(sizeof(ListNode));//greater链表的哨兵头 ltail->next=NULL;//一开始要置NULL gtail->next=NULL; ListNode* cur=pHead;//利用cur进行遍历 while(cur) { if(cur->val<x)//如果小于x就尾插到less的链表中 { ltail->next=cur;//将小的数据尾插到ltail的后面 ltail=ltail->next;//找尾 } else { gtail->next=cur;//将大的数据尾插到gtail后面 gtail=gtail->next; } cur=cur->next;//每次cur也要往后走 } ltail->next=Gguard->next;//让两个链表链接起来 gtail->next=NULL;//想一想这一步是为什么呢？因为最后7的next还链接着2呀，这样就造成回环了。 所以需要将gtail的next置为NULL pHead=Lguard->next;//第一个结点 free(Lguard);//释放 free(Gguard);//释放 return pHead;//返回第一个结点地址 } };
🟩4.链表的回文结构
我们看到链表时有时就会想转空子，想先使用数组来存储链表的数据，然后再进行判断，我们在知道链表长度的前提下理论上是可以的，但最好不要这样做，如果不知道长度，我们还需要动态增容等，所以要抛弃这个想法。
那怎么判断回文结构呢？
回文结构也就是对称，从中间对称，左边与右边对称，如果我们把右边逆转下，那么右边就和左边一样了。所以我们就可以根据左边和右边是否一样进行判断了
- 首先我们需要找到中间结点
- 逆转中间结点以后的结点
- 从逆转开始的位置与开头进行比较
逆转链表，查找链表的中间结点我都已经写过了，这里直接就复制过来。
class PalindromeList { public: struct ListNode* middleNode(struct ListNode* head)//找链表中间结点 { struct ListNode *fast,*slow; fast=slow=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head)//反转链表 { struct ListNode* cur = head; struct ListNode* newnode = NULL; while (cur) { //首先要记录下来cur后面结点的地址 struct ListNode* next = cur->next; //头插 cur->next = newnode; newnode = cur;//更新头指针 cur = next;//cur要往后走 } return newnode; } bool chkPalindrome(ListNode* phead) { ListNode *mid= middleNode(phead);//找中间结点 ListNode *rhead = reverseList(mid);//逆转中间结点以后 //比较链表前面数据与逆转后的数据 while(rhead)//当逆转后的结点走到NULL时结束 { if(rhead->val!=phead->val) return false;//当有一个不等于就然后false phead=phead->next; rhead=rhead->next; } return true;//走到这说明都相等 } };
🟦5.相交链表
怎么判断两个链表是否相交呢？
怎么返回这个相交结点呢？
传统思想可能会让链表A中每个结点的地址与链表B中结点的地址都比较一下，当第一次比较相同时，就是相交结点，不过这种方法的时间复杂度为O(N^2)了，不好，有没有让时间复杂度为O(N)的呢？
好的让我来告诉你吧：
如果两个链表是相交的，那么它们的尾结点的地址一定相同，如果尾结点地址不相同那么肯定不相交。
接着让长的链表先走长度差步，然后两个链表再一起走，当两个链表结点地址比较相同时就是相同结点的位置。
所以
- 求出两个链表的长度，判断是否相交。
- 让长度长的链表先走长度差步，然后一起走
- 两个链表结点地址相比，第一次相同的为相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *cur1=headA,*cur2=headB;//用cur1遍历链表A，用cur2遍历链表2 int lena=0; int lenb=0; while(cur1->next)//记录链表A的长度 { cur1=cur1->next; ++lena; } while(cur2->next)//记录链表B的长度 { cur2=cur2->next; ++lenb; } if(cur1!=cur2)//如果链表尾结点不相同那么肯定不相交 return NULL; int gap=abs(lena-lenb);//长度差，但我们不知道哪个链表长 struct ListNode *longlist=headA,*shortlist=headB; if(lenb>lena)//所以我们需要讨论下 { longlist=headB,shortlist=headA; } while(gap--)//让长的链表先走长度差步 { longlist=longlist->next; } while(longlist!=shortlist)//然后两个链表一起走，当没有结点地址相同时则一起走 { longlist=longlist->next; shortlist=shortlist->next; } return longlist;//最后如果有相同的就返回 }
