【链表】算法题（一） ---- 力扣 / 牛客

一、移除链表元素

        移除链表中值为val的元素，并返回新的头节点

思路：

题目上这样说，我们就可以创建一个新的链表，将值不为val的节点，尾插到新的链表当中，最后返回新链表的头节点。

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {if(head==NULL){return NULL;}ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));ListNode* ptail = head;ListNode* pcur = newhead;while (ptail) {if (ptail->val != val) {pcur->next = ptail;pcur = pcur->next;}ptail = ptail->next;}pcur->next=NULL;ListNode* ret = newhead->next;free(newhead);newhead = NULL;return ret;
}

        当然，这个题还有其他思路。

二、反转链表

        将链表反转，并返回反转后的链表的头节点

思路：

        创建三个指针变量，l1，l2，l3（指针初始指向如下图），遍历链表，先让l3=l2->next；再将l2的next指针指向l2；再l1指向l2，l2指向l3（l2下一个节点）；直到遍历结束，结束条件为（l2等于NULL）此时l1指向的就是反转后的链表的头节点。

根据题目给的示例来分析

遍历数组，循环进行一次

l2不等于NULL循环继续

l2不等于NULL循环继续

l2不等于NULL循环继续

l2仍然不等于NULL，循环继续

到这里，l2已经遍历到了NULL，循环结束，此时l1指向的就是反转后链表的头节点，直接返回即可。

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {ListNode* l1,*l2,*l3;l1=NULL;l2=head;while(l2){l3=l2->next;l2->next=l1;l1=l2;l2=l3;}return l1;
}

三、链表的中间节点

        看到这个题，本人一开始的想法是：遍历一遍链表，记录链表的节点个数，然后再遍历一次链表，寻找链表的中间节点；这样实现非常麻烦，现在使用一种新的方法来解决这个问题

思路：快慢指针

        定义两个快慢指针，fast和slow刚开始都指向链表的头节点，fast每次向前走两个节点，而slow指针每次向前走一个节点；最后当fast指针或者fast的next指针为NULL遍历结束；此时slow指向的就是链表的中间节点。

根据题所给的示例分析：
        链表个数为奇数

fast=fsat->next->next;

slow=slow->next;

           

遍历到这里，fast的next指针为空，循环结束；此时slow指向的就是链表的中间节点。

        链表的节点数为偶数

fast=fsat->next->next;

slow=slow->next;

循环到这里，fast为空，循环结束，此时slow指向的节点就是链表的中间节点。

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(head==NULL){return NULL;}ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}

四、合并两个有序链表

        合并两个有序链表，这里创建一个新的链表，将两个链表中较小小的数据依次尾插到新链表中，最后返回新链表的头节点即可。

        注意：这里需要注意，初始的两个链表可能为空，这里需要进判断，如果list1为空，就返回list1；如果list2为空，就返回list1。

根据题目示例分析

        比较l1和l2指向的节点的值大小，l1->val=l2->val（l1的不小于l2的），将l2指向节点尾插到新链表

        此时，l1->val < l2->val，将l1指向的节点尾插到新链表

        此时，l1->val < l2->val，将l1指向的节点尾插到新链表

比较l1和l2指向的节点的值大小，l2->val < l1->val，将l2指向节点尾插到新链表

        比较l1和l2指向的节点的值大小，l1->val=l2->val（l1的不小于l2的），将l2指向节点尾插到新链表

        l2为空，循环结束，这里l1的节点还没全部插到新链表中，这里直接 ptail->next=l1;即可。

注：这里使用动态内存来给newhead开辟空间，记得将其释放掉，养成好习惯。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* l1=list1;ListNode* l2=list2;ListNode* newhead=(ListNode*)malloc(sizeof(ListNode));ListNode* ptail=newhead;while(l1 && l2){if(l1->val<l2->val){ptail->next=l1;l1=l1->next;}else{ptail->next=l2;l2=l2->next;} ptail=ptail->next;}if(l1){ptail->next=l1;}if(l2){ptail->next=l2;}ListNode* ret=newhead->next;free(newhead);newhead=NULL;return ret;
}

五、链表分割

将链表小于x的节点排在其余节点之前，不能改变原来顺序，最后返回排序好的链表的头指针。

思路：

        创建两个链表，一个链表l1，存放值小于val的节点；另一个链表l2，存放值大于等于val的节点。最后将两个链表连接起来，返回l1链表的头节点即可。

这里需要注意：再l2链表的结尾，要将尾节点的next指针置为NULL；

#include <cstddef>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* list1,*l1;l1=list1=(ListNode*)malloc(sizeof(ListNode));ListNode* list2, *l2;l2=list2=(ListNode*)malloc(sizeof(ListNode));ListNode* ptail=pHead;while(ptail){if(ptail->val<x){//尾插到l1里l1->next=ptail;l1=l1->next;}else{l2->next=ptail;l2=l2->next;}ptail=ptail->next;}l2->next=NULL;l1->next=list2->next;ListNode* ret=list1->next;free(list1);free(list2);list1=list2=NULL;return ret;}
};