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

一、移除链表元素

        移除链表中值为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 here
        ListNode* 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;
    }
};