链表经典面试题【典中典】

🟥1.反转链表

方法一：利用双指针逆转方向
将各个结点的连接方向都倒过来，2结点指向1结点，3结点指向2结点等，我们只要将让每个结点的next指向前一个结点的地址

双指针–将指针指向前面，最后一个变成头。两个指针，一前一后
注意点：

• 单链表不能往前走
• 第一个指针首先指向NULL ，第二个指针在后面，这两个指针用来转变指向
  不过这时第二个指针的后面的地址无法知道，这时需要第三个指针用来记录第二个指针后面的结点的地址。
• 当第三个指针往后走的时候可能为NULL，要注意下
  

代码如下：

struct ListNode* reverseList(struct ListNode* head)
{if(head==NULL)//如果链表为空则直接返回NULLreturn NULL;struct ListNode* prev = NULL;//与cur搭配，记录前面的，一开始为NULLstruct 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进行遍历，不要用形参headstruct 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为空则直接返回链表2return list2;if (list2 == NULL)//当链表2为空则直接返回链表1return 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);//释放guardreturn head;
}

🟨3.链表分割

要求将所有小于x的结点排在其他结点之前，且不能改变原来的数据顺序
我们可以这样做：

1. 将小于x的结点插入到一个链表中
2. 将大于x的结点插入到一个链表中
3. 最后将两个链表链接起来。

不过这里我们最好使用带有哨兵头的链表，这样可以减少进行对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;//一开始要置NULLgtail->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置为NULLpHead=Lguard->next;//第一个结点free(Lguard);//释放free(Gguard);//释放return pHead;//返回第一个结点地址}
};

🟩4.链表的回文结构

我们看到链表时有时就会想转空子，想先使用数组来存储链表的数据，然后再进行判断，我们在知道链表长度的前提下理论上是可以的，但最好不要这样做，如果不知道长度，我们还需要动态增容等，所以要抛弃这个想法。
那怎么判断回文结构呢？
回文结构也就是对称，从中间对称，左边与右边对称，如果我们把右边逆转下，那么右边就和左边一样了。所以我们就可以根据左边和右边是否一样进行判断了

1. 首先我们需要找到中间结点
2. 逆转中间结点以后的结点
3. 从逆转开始的位置与开头进行比较

逆转链表，查找链表的中间结点我都已经写过了，这里直接就复制过来。
《找链表的中间结点》
《反转链表》

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;//当有一个不等于就然后falsephead=phead->next;rhead=rhead->next;}return true;//走到这说明都相等}
};

🟦5.相交链表

怎么判断两个链表是否相交呢？
怎么返回这个相交结点呢？

传统思想可能会让链表A中每个结点的地址与链表B中结点的地址都比较一下，当第一次比较相同时，就是相交结点，不过这种方法的时间复杂度为O(N^2)了，不好，有没有让时间复杂度为O(N)的呢？

好的让我来告诉你吧：
如果两个链表是相交的，那么它们的尾结点的地址一定相同，如果尾结点地址不相同那么肯定不相交。
接着让长的链表先走长度差步，然后两个链表再一起走，当两个链表结点地址比较相同时就是相同结点的位置。
所以

1. 求出两个链表的长度，判断是否相交。
2. 让长度长的链表先走长度差步，然后一起走
3. 两个链表结点地址相比，第一次相同的为相交结点
   

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *cur1=headA,*cur2=headB;//用cur1遍历链表A，用cur2遍历链表2int 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;//最后如果有相同的就返回
}