【数据结构与算法】合并链表、链表分割、链表回文结构

主页：HABUO🍁主页：HABUO

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

1.合并链表

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：l1 = [1,2,4], l2 = [1,3,4]                          输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []                                          输出：[]

输入：l1 = [], l2 = [0]                                        输出：[0]

分析：这道题我们用最容易想的迭代的方法实现，就是每次比较两个数的大小，然后相互更改其中的链表节点间的顺序即可，具体思想如下所示：

当然你也可以重新建立一个新的链表，然后这样去比，去尾插新的链表，但是那样空间复杂度变为了O(n)不太好，虽然这个题没有要求，但尽量别这样做。

最正常比较过程如下：

while (list1 && list2)
{
    if (list1->val < list2->val)
    {
        if (Tail == NULL)
        {
            Head = Tail = list1;
        }
        else
        {            
            Tail->next = list1;
            Tail = list1;
        }
        list1 = list1->next;
    }
    else
    {
        if (Tail == NULL)
        {
            Head = Tail = list2;
        }
        else
        {
            Tail->next = list2;
            Tail = list2;
        }
        list2 = list2->next;
    }
}

有些细节需要注意，有可能传过来的为NULL，因此我们需要对两个指针进行判断：

if (list1 == NULL)
    return list2;
if (list2 == NULL)
    return list1;

又我们的循环条件为：list1 && list2，因此最后是不list1或者list2必须有一个为NULL，但是另一个肯定还没走到最后，因此需要继续：

if (list1)
{
    Tail->next = list1;
    Tail = list1;
}
if (list2)
{
    Tail->next = list2;
    Tail = list2;
}
return Head;

2.链表分割

题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

示例：

输入：head = [3,2,1,3,4,5,6], x = 4                     输出：[3,2,1,3,5,6]

分析： 前面我们做的题大多采用的时两个伪指针进行操作的，那这里可不可行呢？因为毕竟是单链表，这里的数据也不是有序的，可能存在的情况错综复杂，搞不好我们就丢失了链表的一些数据😖，那我们能不能反过来想呢？当初我们采取两个伪指针时是因为开辟新的内存空间，空间复杂度上满足不了题目要求了，那这里没有要求，我们能不能开辟两个链表空间，一个存放小于x的，一个存储大于x的，最后将这两个链表连在一起是不是就可以了？答案很显然行得通😮。具体思想见下图：

大致思想就是cur走完整个链表之后将smalltail链到bighead就ok了，但是这里有许多的问题需要处理，smallhead与bighead最开始都有可能为NULL，这是不是要分情况，而且链表的第一个数你有可能比x大是不是还有可能比x小啊，是不是还要分情况，我估计大家想到这里又有似曾相识的感觉了，烦😑，诶，我们之前不是也遇到这种情况了，我们怎么做的？大家还记得吗？是不是设置一个哨兵位啊，因此在本道习题当中我们给smallhead和bighead都设置一个哨兵位头节点，返回的时候我们是不是只需要返回头节点的下一个节点即可。

哨兵位头节点的设定如下：

ListNode* SmallHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* SmallTail = SmallHead;
ListNode* BigHead = (ListNode*)malloc(sizeof(ListNode));
ListNode* BigTail = BigHead;
ListNode* cur = pHead;

最正常情况挪动数据如下：

while(cur)
{
    if(cur->val < x)
    {
        ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
        SmallTail->next = temp;
        SmallTail = temp;
        SmallTail->val = cur->val;
    }
    else 
    {
        ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
        BigTail->next = temp;
        BigTail = temp;
        BigTail->val = cur->val;
    }
    cur = cur->next;
}

最后返回新的头节点：

BigTail->next = NULL;
SmallTail->next = BigHead->next;
return SmallHead->next;

这里需要注意为什么要加BigTail->next = NULL，因为我们这里都是建立的新的节点，最后一个节点的next是不是不需要再链接其它节点，那它就是随机初始化的一个地址，我们不置空的话，就有可能导致对内存进行非法访问的问题，还有一种是，我们大于的不建立新空间，在原链表进行操作那此时如果不加这一句代码，就有可能导致带环结构，什么意思呢？见下图，因为最开始你3的next放置的就是1那个节点的地址，那你不置空是不是还是那个1的地址，就有可能导致带环，当然如果你释放那个节点的空间，那是不是又造成了非法访问内存的问题。

3.链表的回文结构

题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：1->2->2->1          返回：true

分析：一般这种链表题它给的都是单链表，你说它坑不坑，就是让你难受😩，但是我劝你别烦，听我娓娓道来😉。前面我们做过了找到中间节点，和反转链表，那这个题能不能用我们前面做过题的一种思想呢？显然是可以的，我们可以找到中间的节点之后，把后半链表逆置，然后从尾和头就可以进行比较了，这就是我们的主体思想可以看下图加以理解，当然也有许多细节需要注意。

对于找到中间节点相信大家都已经很熟悉了，如果还有疑问请翻看本人的前面博客，其中有详细的介绍，在这里我们仅给出代码：

ListNode* fast = A;
ListNode* slow = A;
while (fast != NULL && fast->next != NULL)
{
    slow = slow->next;
    fast = fast->next->next;
}

下面是反转链表，前面博客也有详细的介绍，还有不太熟悉的请翻看。我们当时采用了两种方法，一种是三指针法，和头插法，在本题中人家要求了空间复杂度为O(1)，因此我们采取三指针法，具体如下：

ListNode* reverse_tail = slow;
ListNode* slow_prev = slow;
slow = slow->next;
ListNode* slow_next = slow->next;
while (slow)
{
    slow->next = slow_prev;
    slow_prev = slow;
    slow = slow_next;
    slow_next = slow_next->next;
}

相信细心的朋友会看到很多slow->next，是不是存在人家上来给NULL或者一个和两个节点怎么办？因此我们需要在此之前把这几种情况考虑到。具体如下：

if (slow == NULL || slow->next == NULL)
{
    return false;        
}
if (slow->next == NULL)
{
    if (A->val == slow->val)
        return true;
    else
        return false;
}

那我们最正常情况的判断就是三个节点以上的判断了，具体如下：

//三个节点以上的判断
while (slow_prev != reverse_tail)
{
    if (slow_prev->val == A->val)
    {
        A = A->next;
        slow_prev = slow_prev->next;
    }
    else
    {
        return false;
    }
}

这里需要注意，我们奇偶情况是不是不同，即reverse_tail所处的位置不同啊，奇数是在最中间的位置，偶数是在中间两个位置中的处于下一个的位置。具体情况如下图：

我们进行如下的处理以解决此问题：

//奇偶不同情况的附加条件
if (slow_prev != A)
{
    if (slow_prev->val == A->val)
        return true;
    else
        return false;
}
return true;

这里格外注意，因为我们的判断条件设置成了 slow_prev != reverse_tail如果设置成了其它，有一定可能造成我们前面所介绍的带环，因为这里无论偶数的2还是奇数的3它的next是不是还是存放的我们之前未改动链表的它的下一个节点的地址啊，如下所示，如果使用了它就造成了带环，要小心！

补充：

Node* Head = NULL, * Tail = NULL;使用这种方式定义时一定要注意前面的变量也需要初始化，它不是跟后面一起的，两个都需要独立的进行操作，在做这几道题的时候，我用了这种定义的方式可把我害惨了😵‍💫。

总结：本篇博客介绍了三道题，这三道题不约而同的用到了我们前面所学到的知识，我相信通过这几道题的应用，我们对前面的知识，无论时反转链表、找中间节点等题型都了然于胸，我们也接触到了一个新题型判断链表的回文结构，相信本篇博客的学习我们受益匪浅！💯

🏋不是每一粒种子都能开花，但播下种子就比荒芜的旷野强百倍🏋