反转链表合并两个有序链表链表分割链表的回文结构相交链表

反转链表

来源：杭哥

206. 反转链表 - 力扣（LeetCode）

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{if (head==NULL){return NULL;}ListNode* prev=head;ListNode* cur=head->next;ListNode* fur=NULL;prev->next=NULL;while(cur!=NULL){fur=cur->next;cur->next=prev;prev=cur;cur=fur;}return prev;
}

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{if (head==NULL){return NULL;}ListNode* prev=head;ListNode* cur=head->next;head->next=NULL;ListNode* phead=head;while(cur!=NULL){prev=cur;cur=cur->next;prev->next=phead;phead=prev;}return phead;
}

我想说：

1. 我想说的是，像这种问题的话，就图多画一画就迎刃而解了。

2. 反转链表的话，第一种思路就是利用三指针prev, cur, fur，然后这么倒来倒去就可以了。

3. 第二种方式的话，可以新创建一个链表的头节点，然后把原先列表当中的每一个节点都头插到这个新链表中。

---

合并两个有序链表

来源：杭哥

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

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL){return list2;}if (list2==NULL){return list1;}ListNode* cur1=list1;ListNode* cur2=list2;ListNode* cur=NULL;ListNode* phead=NULL;int flag=0;while(cur1!=NULL && cur2!=NULL){if (cur1->val<cur2->val){if (flag==0){flag=1;phead=cur1;}else{cur->next=cur1;}cur=cur1;cur1=cur1->next;}else{if (flag==0){flag=1;phead=cur2;}else{cur->next=cur2;}cur=cur2;cur2=cur2->next;}}if (cur2!=NULL){cur->next=cur2;}if (cur1!=NULL){cur->next=cur1;}return phead;
}

#include <stdlib.h>
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* cur1=list1;ListNode* cur2=list2;ListNode* guard=(ListNode*)malloc(sizeof(ListNode));guard->next=NULL;ListNode* cur=guard;while(cur1!= NULL && cur2!= NULL){if (cur1->val < cur2->val){cur->next= cur1;cur=cur1;cur1=cur1->next;}else{cur->next= cur2;cur=cur2;cur2=cur2->next;}}if (cur1==NULL){cur->next=cur2;}if (cur2==NULL){cur->next=cur1; }return guard->next;
}

我想说：

1. 带哨兵位的头结点的单链表的好处在于可以回避掉许多因为空指针而带来的麻烦。

2. 两个链表的合并实际上就类似于归并的思想。

---

链表分割

来源：杭哥

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

#include <stdlib.h>
class Partition {
public:ListNode* partition(ListNode* pHead, int x){ListNode* guard1 = (ListNode*)malloc(sizeof(ListNode));guard1->next=NULL;ListNode* cur1=guard1;ListNode* guard2 = (ListNode*)malloc(sizeof(ListNode));guard2->next=NULL;ListNode* cur2=guard2;ListNode* cur=pHead;while(cur!=NULL){if (cur->val< x){cur1->next=cur;cur1=cur;}else{cur2->next=cur;cur2=cur;}cur=cur->next;}cur1->next=guard2->next;cur2->next=NULL;return guard1->next;}
};

我想说：

1. 如果想要回避掉空指针所带来的一系列麻烦，创建新的单链表的时候就选择带哨兵位头结点的单链表形式。

---

链表的回文结构

来源：杭哥

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

class PalindromeList {
public:bool chkPalindrome(ListNode* A){int count=1;ListNode* slow=A;ListNode* fast=A;while(fast!=NULL && fast->next!=NULL){slow=slow->next;count++;fast=fast->next->next;}ListNode* prev=slow;ListNode* cur=prev->next;ListNode* fur=NULL;ListNode* head=NULL;prev->next==NULL;while(cur!=NULL){fur=cur->next;cur->next=prev;count++;prev=cur;cur=fur;}head=prev;int num=count/2;while(num--){if (A->val != head->val){return false;}A=A->next;head=head->next;}return true;}
};

我想说：

1. 通过快慢指针（双指针）可以找到链表的中间节点。

2. 对中间节点及其后面的链表部分反转，然后与前面那一段进行节点数值一一比较。

---

相交链表

来源：杭哥

160. 相交链表 - 力扣（LeetCode）

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{int len1=1;int len2=1;ListNode* cura=headA;ListNode* curb=headB;while(cura->next!=NULL){len1++;cura=cura->next;}while(curb->next!=NULL){len2++;curb=curb->next;}if (cura!=curb){return NULL;}int gap=abs(len1-len2);ListNode* longlist=headA;ListNode* shortlist=headB;if (len1<len2){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

我想说：

1. 链表相交的话，不是成十字形状的，而是类似于剪刀这种形状，因为一个节点的next指针不可能指向两个位置。

2. 如果说两个链表的尾节点地址是相同的，那么这两个链表一定是相交的。