扬帆数据结构算法之雅舟航程，漫步C++幽谷——LeetCode刷题之移除链表元素、反转链表、找中间节点、合并有序链表、链表的回文结构

人无完人，持之以恒，方能见真我！！！
共同进步！！

一、移除链表元素

题目链接：移除链表元素
我们先来看看题目的描述

根据题目描述我们就可以大致明白题意，就是将一个链表中的某个值的节点删除，然后返回新链表的头结点，然后题目要我们实现的函数给了我们头结点，以及要删除的数据，我们要把相应的节点删除

思路一

首先最简单的思路就是，我们可以通过之前实现的链表的方法用上，首先使用Find方法找到对应的值，然后使用Erase方法删除，直到Find方法返回空指针结束

由于这个方法思路比较好实现，这里就不再赘述了，可以自己尝试一下，我们的关键是更优方法的思路二

思路二

这个题其实跟我们在刷顺序表题的时候遇见类似的，只不过之前要删除的是数组中的元素，这道题是删除链表节点，不过本质上是相同的，上次我们使用了双指针，这次我们还是可以使用双指针

具体思路也很像之前的那个题，题目让返回新链表的头结点，没有说必须是原链表的头结点，所以我们可以新建一个链表，如果遍历到原链表中节点的值不是题目给定的值，也就是不是我们要删除的节点，那么我们就把它尾插到新链表

我们要注意的是，如果遇到了要插入的节点，但是新链表的头为空，我们就要让新链表的头和尾都指向这个节点，其它情况就正常尾插

还有一个重要的地方就是，当我们把链表移动完毕之后，新链表的尾结点可能还指向原链表的节点，我们要把它置为空，题解如下：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    ListNode* newhead, *newtail;//定义新链表的头尾节点
    newhead = newtail = NULL;//首尾都指向自己
    ListNode* pcur = head;//定义新链表的当前节点

    while(pcur)
    {
        if(pcur->val != val)
        {
            //这里是首节点的判断节点
            if(newhead == NULL)
            {
               newhead = newtail = pcur;
            }
            else
            {
                newtail->next = pcur;
                newtail = pcur;
            }
        }
        pcur = pcur->next;//继续向后走
    }
    if(newtail)
        newtail->next = NULL;//如果尾结点不为空，就置空尾结点的next
    return newhead;//返回新的头结点
}

二、合并两个有序链表

题目链接：合并两个有序链表

题目给我们两个有序链表，要求我们把这两个链表合并成一个新的有序链表，然后返回它的头结点

思路：

这个问题是不是有点似曾相识，跟我们之前的合并有序数组是一样的，我们当时的方法就是使用双指针，只是合并有序数组时是要求我们在第一个数组中进行修改，不能新建一个数组返回

但是这道题还要简单一些，它可以新建一个链表，我们可以通过双指针遍历要合并的链表，比较两个链表中节点的大小，谁小谁就尾插到新链表，直到有一个链表走到空就停止循环

但是我们要注意的一点是，虽然有一个链表走到空了，也就是一个链表中的节点都插入到新链表了，但是另一个链表可能还有节点，所以我们要判断一下，如果两个链表中还有一个链表不为空，那么直接将它的所有节点尾插到新链表

还有就是做一个特殊处理，因为两个链表中可能有空链表，上面的方法就跑不通，所以我们判断一下，如果有一个链表为空，那么直接返回另一个链表，题解如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    //首先对特殊情况进行处理
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    //赋值头结点
    struct ListNode* pcur1 = list1, *pcur2 = list2;
    //记录头结点和尾结点
    struct ListNode* newhead = NULL,*newtail = NULL;
    
    //进入循环开始判断
    while(pcur1 && pcur2)
    {
        if(pcur1->val < pcur2->val)
        {
            if(newhead == NULL)//首节点是空说明没有节点
            {
                newhead = newtail = pcur1;
            }
            else
            {
                newtail->next = pcur1;
                newtail = pcur1;//赋值新的尾结点
            }
            pcur1 = pcur1->next;
        }
        else
        {
            if(newhead == NULL)//首节点是空说明没有节点
            {
                newhead = newtail = pcur2;
            }
            else
            {
                newtail->next = pcur2;
                newtail = pcur2;//赋值新的尾结点
            }
            pcur2 = pcur2->next;
        }
    }
    //走出循环再对两个链表进行判空
    if(pcur1)
    {
        newtail->next = pcur1;
    }
    if(pcur2)
    {
        newtail->next = pcur2;
    } 
    
    return newhead;
}

优化：

上面的代码是一种题解，但是我们可以发现，这个代码写起来有点麻烦，有一些重复的动作，就是在每次插入之前，我们要判断链表是否为空，如果为空要让新链表的头和尾都指向要插入的节点

那我们能不能让代码更加简洁一点呢？就是不必每次插入节点前都判断链表是否为空，这里就可以用上我们之前学过的带头的概念，我们申请一个不保存数据的哨兵位当作链表默认的头

这样我们的新链表默认就有了一个节点，不为空了，可以直接在哨兵位后面尾插节点，不用判断链表是否为空，最后返回时就返回哨兵位的下一个节点就可以了，它就是我们新链表中保存数据的头节点

不过由于我们的哨兵位是通过malloc来的，所以最后代码结束时不要记得把它释放掉，以免造成内存泄漏，如下：

上面的代码是一种题解，但是啊我们可以发现这个代码写起来还是有一些麻烦的，多了一些重复的动作，就是在每次尾插链表前，我们都要判断链表是否为空，如果为空就要让新链表的头和尾都要指向要插入的节点

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    //赋值头结点
    struct ListNode* pcur1 = list1, *pcur2 = list2;
    //创建哨兵位
    struct ListNode* guard = NULL,*tail = NULL;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;//将尾结点置空

    //循环找小,并链接
    while(pcur1 && pcur2)
    {
        if(pcur1->val < pcur2->val)
        {
            tail->next = pcur1;
            tail = tail->next;
            pcur1 = pcur1->next;
        }
        else
        {
            tail->next = pcur2;
            tail = tail->next;
            pcur2 = pcur2->next;
        }
    }
    //当两个链表有一个走完，就将另一链表链接过来
    if(pcur1)
    {
        tail->next = pcur1;
    }
    if(pcur2)
    {
        tail->next = pcur2;
    }
    //创建一个返回头结点的节点
    struct ListNode* head = guard->next;
    free(guard);//在返回结果前，释放哨兵位
    return head;
}

三、反转链表

题目链接：反装链表

题目要求我们将给出的链表反转，就是改变指针的指向，让原本的尾节点变成头，让原本的头结点变成尾

思路一

思路一还是很简单，就是我们创建一个新链表，遍历原链表，拿原链表中的节点头插到新链表就可以了，如图：

有了上图的分析，实现就很简单了，只需要一个头插方法，我们之前讲过，这里就不再赘述了，可以自己试试，我们重点介绍思路二

struct ListNode* reverseList(struct ListNode* head) {
     struct ListNode* cur = head,*newhead = NULL;
    //赋值当前节点，创建一个新的头结点
    while(cur)
    {
        //保存下一个节点
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

思路二

思路二是对原链表的节点的指针指向进行修改，所以很快，并且不会消耗什么空间，思路如图：

有了上面的思路我们就可以开始写代码了，但是我们需要注意的一个点就是，如果测试样例是空链表的话，那么我们就还是需要特殊处理一下，如果链表为空，我们就直接返回，因为空链表没有反转的必要，题解如下:

struct ListNode* reverseList(struct ListNode* head) 
{
    //首先对空链表进行判断
    if(head == NULL)
    {
        return head;
    }
    struct ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    //当n2为空，结束循环
    while(n2)
    {
        n2->next = n1;
        //改变指向后，三个指针都向后走
        n1 = n2;
        n2 = n3;
        //n3不为空就继续向后走
        if(n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

四、链表的中间节点

题目链接：链表的中间节点

先来看看题目描述:

它的要求就是让我们返回链表的中间节点，如果是偶数个节点，那么就有两个中间节点，则返回后一个节点

思路一

第一个很简单的方法就是，先遍历整个链表，看看总共有多少个节点，然后让总数除2，最后再次遍历链表就可以找到中间节点，这个题很简单，我们这里直接给出题解

struct ListNode* middleNode(struct ListNode* head) 
{
    int count = 0;//定义计数变量
    struct ListNode* pcur = head;
    while(pcur)//循环计数
    {
        count++;
        pcur = pcur->next;
    }
    count /= 2;
    pcur = head;//重新赋值，找中间结点
    while(count--)
    {
        pcur = pcur->next;
    }
    return pcur;//找到中间节点，返回
}

思路二

思路二的方法很绝妙，简单又快捷，就是使用快慢指针的算法，快慢指针默认都指向头结点，慢指针一次走一步，快指针一次走两步，那么等快指针走到空的时候，慢指针指向的节点就是中间节点

为什么呢？因为快指针每次走的距离都是慢指针的2倍，最后统计一共走的距离时，快指针走的总距离也是慢指针的2倍，而快指针走到了空，也就说明走到了链表尾，那么此时慢指针就是它的一半，刚好指向中间节点，题解如下：

思路二的方法很绝白，鉴定饭店有快捷，就是使用我们快慢指针的办法，快慢指针都指向头结点，慢指针一次走一步，快指针一次走两步，那么等快指针走到空的时候，慢指针指向的节点就是中间节点

struct ListNode* middleNode(struct ListNode* head) 
{
    struct ListNode* fast,* slow;
    fast = slow = head;
    while(fast && fast->next)//判断链表是空和快指针走到空的循环条件
    {
        slow = slow->next;//走1步
        fast = fast->next->next;//走2步
    }
    return slow;//此时慢指针就是中间节点
}

五、综合应用之链表的回文结构

题目链接：链表的回文结构

先来看看题目描述:

题目要求我们判断给出的链表是否是一个回文结构，也就是是否前后对称，这道题就可以用上我们之前做题写出的代码，具体后面再说，我们先解决一个事情

就是这个题目没有提供C语言的选项，那我们就选择C++来做，C++是兼容C语言的，主要是我们要知道在哪里写代码，如图：

这是C++中的类，但是不影响我们做题，我们只需要知道我们把代码写在哪里，在题目中也有提示，把代码写在紫色大括号内即可，其它的可以不管，还有一个就是，C++对结构体做了优化，可以在使用结构体时不必加上struct

思路一

虽然判断链表是否是回文结构很难，但是我们可以把链表中的数据存放到数组中，判断数组是否是回文结构，这个就比较简单了

由于链表两边的数据是对称的，所以我们定义一个left和right分别指向数组的头和尾，然后对比它们的值，如果不同直接返回假，否则的话就一直让它们往中间走，直到left不再小于right

在循环过程中，一旦left所在位置的值和right所在位置的值不相同，就说明并不对称，也就不是回文结构，返回假，一旦循环结束，说明左右对称，就是回文结构，直接返回真

并且我们注意到，虽然题目要求空间复杂度为O(1)，但是同时又给出了链表的最大节点个数不超过900，那定义一个901个元素大小的数组时间复杂度还是O(1)，因为它始终还是常数个空间，如下：

class PalindromeList {
public:

bool chkPalindrome(ListNode* A) 
{
        int arr[901] = { 0 };
        ListNode* pcur = A;
        int i = 0;
        //先用数组存储链表的val
        while(pcur)
        {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        int left = 0, right = i-1;
        //循环比较数组的val
        while(left < right)
        {
            if(arr[left] != arr[right])
            {
                return false;//不相同就返回false
            }
            left++, right--;//分别向中间走
        }
        return true;//走出循环就是回文结构
}
};

思路二

这个思路可以帮我们复习上面做过的题，让我们能够灵活运用知识，具体思路就是，我们首先通过找中间节点的函数找到链表中间节点，然后从中间节点开始，将后面的节点反转，形成一个新链表，然后再和原链表进行比较即可，如图：

找中间节点的函数和反转链表的函数可以从我们之前做过的题里面拿过来用，当然也可以自己根据这个逻辑把中间的代码实现，这里我就直接把之前写过的函数直接拿过来用，如下：

class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) 
{
     struct ListNode* cur = head,*newhead = NULL;

    while(cur)
    {
        //保存下一个节点
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

struct ListNode* middleNode(struct ListNode* head) 
{
    struct ListNode* fast,* slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

bool chkPalindrome(ListNode* head) 
{
      struct ListNode* mid = middleNode(head);
      struct ListNode* rhead = reverseList(mid);

    while(head && rhead)
    {
        //先判断
        if(head->val != rhead->val)
            return false;

            head = head->next;
            rhead = rhead->next;
    }
    return true;
}
};

那么今天的Leetcode刷题就到这里了，bye~