三板斧解决leetcode的链表题

在《波奇学单链表》中我们提到单链表的两个特点

1. 单向性。

2. 头节点尾节点的特殊性导致分类讨论的情况。

如何看单链表？

让我们简化成下图

cur表示当前节点，下图表示cur移动，圆圈表示值

用哨兵卫节点(新的头节点)和把尾节点看成NULL来把头尾节点一般化。

struct ListNode*guard_h=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*cur=guard_h;//作为移动节点

相当于有了头节点的前驱节点，可以cur->next=cur->next->next;循环

删除尾节点不用cur->next=NULL(cur是4的地址)直接cur->next=cur->next->next;

简化代码，但要注意释放开辟的空间，避免内存泄露。

快慢指针

创建两个指针一快一慢。

快慢指针找链表的中间节点：leetcode 876.链表中间节点

struct ListNode*fast=head,*slow=head;
int count=0;
while(fast)
{fast=fast->next;count++;if(count%2==0){slow=slow->next;}
}
return slow;//结束时fast为空，slow为中间节点的右边节点

变式：求中间节点的左节点（如1-2-3-4求2）

fast走的节点数=总节点数，fast和slow指针走的节点数如图。

struct ListNode*fast=head,*slow=head;
int count=0;
while(fast)
{fast=fast->next;count++;if(count%2==1&&count>=3){slow=slow->next;}
}
return slow;//结束时fast为空，slow为中间节点的左边节点

反转链表

leetcode：反转单链表

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){//next指针指向cur的下个节点struct ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}

合并有序链表

leetcode：合并有序链表

思路：不要试图在原链表中进行插入操作，再开一个新的头节点，把原来链表的值拿过来链接。

用哨兵节点可以简化代码，短的拼完后，再把剩下的链接在一起就行。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*cur=(struct ListNode*)malloc(sizeof(struct ListNode));cur->next=NULL;cur->val=0;struct ListNode*head=cur;while(list1&&list2){if(list1->val>list2->val){head->next=list2;list2=list2->next;}else{head->next=list1;list1=list1->next;}head=head->next;}struct ListNode*list3=(list1!=NULL?list1:list2);while(list3){head->next=list3;list3=list3->next;head=head->next;}return cur->next;
}

合并链表，快慢指针，以及链表逆序这三板斧掌握了就可以解决leetcode上大部分的链表题。

示例：链表排序

思路：快慢指针找中间节点，再用中间节点不断分割，分割到只有一个节点或空链表。

一节点链表进行合并有序链表，最后把新链表再进行合并有序直到所有链表都合并完成。

总而言之，最基础就是这三个。