编号0011 分割链表

解法一

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要保留每个分区中各节点的初始相对位置。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/partition-list-lcci

我们来看图

其实这个题目解释起来也简单

我们要将整个数组所有小于x的值放在x的左边

所有大于x的值放在x的右边

解决这个问题我们可以设计两个新链表

然后遍历链表如果遍历到的元素小于x我们就将它放到创造的第一个链表当中

如果遍历到的元素大于x我们就就将它放到创造的第二个链表当中

我们这里提交代码

发现最后这里出错了

检查下发现我们忽略了两种特殊情况

如果都大于或者都小于呢

所以我们补上后面的代码

加上后面这段代码之后就能过了

代码完整表示如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x)
{
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* lesshead = NULL;
    struct ListNode* betterhead = NULL;
    struct ListNode* lesstail = NULL;
    struct ListNode* bettertail = NULL;
    struct ListNode* pos = head;
    //  pos节点指向空的时候就不进去了  注意结束条件
    while(pos)
    {
        if(pos->val<x)
        {
            if(lesshead==NULL)
            {
                lesshead=lesstail=pos;
            }
            else
            {
                // 尾插数据 注意这里其实lesstail=pos也一样
                lesstail->next=pos;
                lesstail=lesstail->next;
            }
        }
        else
        {
            if(betterhead==NULL)
            {
                betterhead=bettertail=pos;
            }
            else
            {
                //写一种不同的写法 方便大家理解
                bettertail->next = pos;
                bettertail = pos;
            }
        }
        pos=pos->next;
    }
    if(lesstail==NULL)
    {
        return betterhead;
    }
    if(bettertail==NULL)
    {
        return lesshead;
    }
    lesstail->next = betterhead;
    bettertail->next = NULL;
    return lesshead;
}

解法二

除了上面那一种解法之外我们还可以使用一个新的解法

利用我们学到的基础知识头插尾插

如果这个数小于我们规定的值就头插到新链表

如果这个数大于等于我们规定的值就尾插到新链表

画图表示如下

代码表示如下

struct ListNode* partition(struct ListNode* head, int x)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    struct ListNode* newtail = NULL;
    struct ListNode* pos = head;
    struct ListNode* next = head;
    while (next)
    {
        next = next->next;
        if (pos->val < x)
        {
            pos->next = newhead;
            newhead = pos;
            if (newtail==NULL)
            {
                newtail = newhead;
            }
        }
        else
        {
            if (newhead == NULL)
            {
                newhead = head;
                newtail = head;
                newtail->next = NULL;
            }
            else
            {
                newtail->next = pos;
                pos->next = NULL;
                newtail = pos;
            }
        }
        pos = next;
    }
    return newhead;
}

这里要注意的是在既要头插又要尾插的问题中

第一次赋值的时候一定要把第一个数组的next赋值给空指针

编号0012 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解法一

这里我们有很多种解法

我们先给一种时间复杂度O（N）空间复杂度O（N）的数组法

还是直接上图

上代码

bool isPalindrome(struct ListNode* head)
{
    if(head==NULL)
    {
        return true;
    }
    int* num_val = (int *)malloc(sizeof(int)*100001);
    int count =0;
    struct ListNode* pos =head;
    while(pos)
    {
        num_val[count++]=pos->val;
        pos = pos->next;
    }
    int left =0;
    int right = count-1;
    while(left<right)
    {
        if(num_val[left]!=num_val[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

很简单的解法也不需要多讲什么了

只有一点要注意的是

空链表是回文链表

解法二

这个解法就比较有难度了

但是它能够将我们的空间复杂度降低至O（1）

我们首先写两个函数

一个寻找中间节点

一个逆序单链表

代码表示如下

struct ListNode* Findhalf(struct ListNode* head)
{
    assert(head);
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while((fast!=NULL)&&(fast->next!=NULL))
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
struct ListNode* reversehalf(struct ListNode* half)
{
    // 这里其实补判断空指针也可以 不过大家尽量养成一个好习惯 
    if(half == NULL)
    {
        return NULL;
    }
    struct ListNode* prev =NULL;
    struct ListNode* pos =half;
    struct ListNode* next =half;
    while(pos)
    {
        next=next->next;
        pos->next = prev;
        prev = pos;
        pos =next;
    }
    return prev;
}
bool isPalindrome(struct ListNode* head)
{
    if(head==NULL)
    {
        return true;
    }
    struct ListNode* half =NULL;
    struct ListNode* halfstart =NULL;
    // 找到中间节点 
    half = Findhalf(head);
    // 翻转中间节点 
    halfstart = reversehalf(half);
    // 比较两个链表 
    struct ListNode* p1 =head;
    struct ListNode* p2 =halfstart;
    while(p1&&p2)
    {
        if(p1->val!=p2->val)
        {
            return false;
        }
        p1=p1->next;
        p2=p2->next;
    }
    return true;
}

编号0013 双链表相交节点

输入两个链表，找出它们的第一个公共节点。

这道题目也很简单

使用双指针法就可以轻松解决

如下图

如果它们有交点

那么它们就会在交点处相遇

如果它们没有交点

那么它们就会在空指针处相遇

代码表示如下

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    if(headA==NULL)
    {
        return NULL;
    }
    if(headB==NULL)
    {
        return NULL;
    }
    struct ListNode *l1 =headA;
    struct ListNode *l2 =headB;
    while(l1!=l2)
    {
        l1=l1==NULL?headB:l1->next;
        l2=l2==NULL?headA:l2->next;
    }
    return l2;
}

编号0014 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/linked-list-cycle

还是先上图

我们先来看有环的情况

这个时候实际上fast和slow会在里面陷入死循环

我们把这个图再抽象下

实际上就是一个这样子的图形

大家有没有表示眼熟？

这不就是我们的操场吗

那么我们把问题变一下

两个人跑步一个跑的比较快一个跑的比较慢

如果在一个直线的操场上它们会相遇嘛？

显然不会

但是如果在一个环形的操场上呢？

那必然会啊

那么我们接着来看

所以说这里就论证了当fast=2 slow=1时

它们在某个节点相遇的必然性

所以这个时候我们就可以上手写代码了

代码表示如下

bool hasCycle(struct ListNode *head) 
{
    if(head==NULL || head->next == NULL)
    {
        return NULL;
    }
    struct ListNode * fast = head->next;
    struct ListNode * slow = head;
    while(fast!=NULL && fast->next!=NULL)
    {
        if(slow==fast)
        {
            return true;
        }
        else
        {
            slow = slow->next;
            fast = fast->next->next;
        }
    }
    return false;
}

编号0015 环形链表二

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/linked-list-cycle-ii

这一题跟上一题一样

这样子就证明了

一个slow指针从起点开始走

一个slow指针从遇见的点开始走

它们会在环的起点相遇

代码表示如下

struct ListNode *detectCycle(struct ListNode *head) 
{
    if(head==NULL || head->next==NULL)
    {
        return NULL;
    }
    struct ListNode *slow =head;
    struct ListNode *fast =head;
     struct ListNode *cur =head;
    struct ListNode *pos  =NULL;
    struct ListNode *meet  =NULL;
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            meet = fast;
            while(meet!=cur)
            {
                cur=cur->next;
                meet=meet->next;
            }
            pos = meet;
            return pos;
        }
    }
    return NULL;
}