手撕算法题2（附源码和思路）

1.移除链表元素

移除链表元素

这道题有三个思路

• 遍历链表找到要删除的结点然后再循环里面调用SLTErase函数（我博客单链表的实现写过了也涵盖了结点为头结点的情况）
• 递归
• 创建新链表(最简单)

设计程序

遍历链表

将链表中非val的值赋给新链表

注意新链表的尾结点仍然指向旧链表因此一定要将尾结点的next结点置为空指针

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 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=NewTail->next;
            }
        }
        pcur=pcur->next;
    }
    if(NewTail)
    NewTail->next=NULL;
    return NewHead;
}

2.反转链表

反转链表

这道题有三个思路

• 创建新链表进行头插
• 递归
• 双指针

设计程序

创建三个指针一个n1指针指向NULL，一个n2指针指向头结点，一个指针n3保存n2指针的next结点
遍历链表

将n2的next指针指向n1（此时我们就找不到下一个结点所以要用到n3）
n1变为n2，n2变为n3，n3变为n3的next结点
循环上述过程

n1即为新的头结点

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
     if(head==NULL)
    return NULL;
    ListNode*n1=NULL;
    ListNode*n2=head;
    ListNode*n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    return n1;
}

2.链表的中间结点

链表的中间节点
设计程序

创建一个快指针和一个慢指针，两个指针都指向头结点
用快指针遍历链表（分偶数个结点个数和奇数个结点个数）

快指针每次走两步，慢指针每次走一步

遍历结束慢指针即为中间结点

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode*fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

3.合并两个有序链表

合并两个有序链表

设计程序

创立一个新链表
遍历两个链表

比较两个链表数据大小尾插到新链表中

退出循环时其中一个链表还没有遍历完，尾插没遍历完的链表

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
        ListNode*NewHead=NULL,*NewTail=NULL;
        if(list1==NULL)
        return list2;
        if(list2==NULL)
        return list1;
        while(list1&&list2)
        {
            if(list1->val>list2->val)
            {
                if(NewHead==NULL)
                {
                    NewHead=NewTail=list2;
                }
                else
                {
                    NewTail->next=list2;
                    NewTail=NewTail->next;
                }
                list2=list2->next;
            }
            else
            {
            if(NewHead==NULL)
                {
                    NewHead=NewTail=list1;
                }
                else
                {
                    NewTail->next=list1;
                    NewTail=NewTail->next;
                }
                list1=list1->next;
            }
        }
        while(list1)
        {
            NewTail->next=list1;
            NewTail=NewTail->next;
            list1=list1->next;
        }
        while(list2)
        {
            NewTail->next=list2;
            NewTail=NewTail->next;
            list2=list2->next;
        }
        return NewHead;
}

当然我们都要判断NewHead是否为空代码太冗杂我们可以malloc一个结点，往这个结点进行尾插，最后我们返回这个结点的下一个结点并把这个结点free这样就避免了判断头结点是否为空的情况。接下来这道题的话就可以malloc一个结点避免判断头结点是否为空。

4.链表分割

链表分割
设计程序

创建两个新链表（大链表和小链表），遍历原链表将小于x的结点尾插到小链表中，大于等于x的结点尾插到大链表中，之后将大链表的尾结点的next结点置为NULL，最后将两个结点(小链表的尾结点和大链表头结点的下一个结点)连接起来。

编写代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode*LessHead,*LessTail,*GreatHead,*GreatTail;
        LessTail=LessHead=(ListNode*)malloc(sizeof(ListNode));
        GreatTail=GreatHead=(ListNode*)malloc(sizeof(ListNode));
        ListNode*pcur=pHead;
        while(pcur)
        {
            if(pcur->val<x)
            {
                LessTail->next=pcur;
                LessTail=LessTail->next;
            }
            else
            {
                GreatTail->next=pcur;
                GreatTail=GreatTail->next;
            }
            pcur=pcur->next;
        }
        GreatTail->next=NULL;
        LessTail->next=GreatHead->next;
        return LessHead->next;
    }
};

其实这段代码还有一部分缺陷那就是我没有释放内存块，应该保存要返回的结点，然后释放我们开辟的两个头结点

5.链表的回文结构

链表的回文结构

思路

• 创建一个数组（其实这道题我没截全，它链表的数量最多为900，int arr[900]，常数空间复杂度为O（1）），遍历链表存进数组（记得找一个计数器记录数据有效个数），从头和尾进行比较
• 利用快慢指针和反转链表

这里我分享第二种思路
设计程序

封装两个函数一个找中间结点和一个逆置链表
找到中间结点进行逆置
遍历逆置后的链表与原链表比较，相同跳到next指针，不同则返回false
跳出循环返回true

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
ListNode* FindMid(ListNode*phead)
        {
            ListNode*fast,*slow;
            fast=slow=phead;
            while(fast&&fast->next)
            {
                slow=slow->next;
                fast=fast->next->next;
            }
            return slow;
        }
ListNode* Reverse(ListNode*phead)
{
ListNode*n1,*n2,*n3;
n1=NULL;
n2=phead;
n3=phead->next;
while(n2)
{
    n2->next=n1;
    n1=n2;
    n2=n3;
    if(n3)
    n3=n3->next;
}
return n1;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        //1.找中间结点
         ListNode*mid=FindMid(A);
        //2.逆置链表
        ListNode*right=Reverse(mid);
        ListNode*left=A;
        while(right)
        {
            if(right ->val==left->val)
            {
                right =right->next;
                left =left->next;
            }
            else return false;
        }
        return true;
    }
};

6.相交链表

相交链表
设计程序

遍历两个链表直到找到相同的结点为止
分两种情况（两链表等长，两链表不等长）
长链表走掉两链表的差值进入循环

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int size1=0,size2=0;
    ListNode*n1=headA,*n2=headB;
    while(n1)
    {
        size1++;
        n1=n1->next;
    }
     while(n2)
    {
        size2++;
        n2=n2->next;
    }
    int gap=abs(size1-size2);//abs返回的是绝对值
    ListNode*LongList=headA;
    ListNode*ShortList=headB;
    if(size1<size2)
    {
        LongList=headB;
        ShortList=headA;
    }
    while(gap--)
    {
        LongList=LongList->next;
    }
    while(LongList&&ShortList)
    {
        if(LongList==ShortList)
        return LongList;
        LongList=LongList->next;
        ShortList=ShortList->next;
    }
    return NULL;
}

7.环形链表

重点

推导

这个环是逆时针走的

入口到相遇点的距离为b，相遇点到入口的距离为c
环长=b+c
慢指针运动的距离 slow=a+b
快指针运动的距离为 fast=a+b+k(b+c)
若快慢指针相遇 2slow=fase
2(a+b)=a+b+k(b+c);
a-c=(k-1)(b+c);
此时从头结点出发走c布就会遇到环了（不是进入环而是说遇到了环的终点），而相遇点走c布也就会到环的终点（尾结点是环的起点，尾结点的next指针指向的地方便是环的终点）

上述过程是我们假设快慢指针一定会在环在环中相遇，但是怎么证明快慢指针一定相遇这里借用下大佬的评论

这个问题还可以引申如果快指针走m，慢指针走n步，快慢指针一定相遇吗
我们代入上式子最后可以得到(m-n)(a-c)=(k-m+n)(b+c)这样一个式子一定有解就意味着存在（我也不知道是否可以这样理解）但是我翻遍一些资料也没找到了证明了其他的情况，可能a,b,c有一定的关系但是我也找不不太清楚，如果有人明白的话可以分享了一下

分享一下快指针走三步慢指针走一步差为2
N为慢指针入环时，快慢指针的距离差

所以说追上的情况一定是C和N同为奇数或偶数，而且C和N一定同为奇数和偶数（但我无法证明）。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
     ListNode*slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        return true;
    }
    return false;
}

8.环形链表II

上面讲过了

编写代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode*slow,*fast,*meet;
    meet=NULL;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            ListNode*pcur=fast;
            while(pcur!=head)
            {
                pcur=pcur->next;
                head=head->next;
            }
            return pcur;
        }
    }
    return NULL;
}

9.随机链表的复制

随机链表的复制
思路

• 在原链表的基础上复制链表
• 置random指针
• 复制链表和原链表断开
  
  设计程序
  封装一个BuyNode方法复制结点，注意把random和next指针都置为NULL
  AddNode把链表和新的结点连接起来，注意先将新结点连接起来，当然你也可以先把旧结点连接不过这样的话你就要保存一下下一个结点
  置random指针这里一定要画图
  分离链表一定要注意空指针的情况，为什么我这里不直接

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* BuyNode(int x)
{
    Node* NewNode=(Node*)malloc(sizeof(Node));
    NewNode->val=x;
    NewNode->next=NULL;
    NewNode->random=NULL;
    return NewNode;
}
void AddNode(Node*head)
{
    Node*pcur=head;
    while(pcur)
    {
        Node*NewNode=BuyNode(pcur->val);
        NewNode->next=pcur->next;
        pcur->next=NewNode;
        pcur=NewNode->next;
    }
}
struct Node* copyRandomList(struct Node* head) {
	if(head==NULL)
    return NULL;
    AddNode(head);
    Node*pcur=head;
    while(pcur)
    {
        if(pcur->random)
        pcur->next->random=pcur->random->next;
        pcur=pcur->next->next;
    }
    pcur=head;
    Node*NewHead,*NewTail;
    NewHead=NewTail=pcur->next;
    while(pcur->next->next)
    {
        pcur=pcur->next->next;
        NewTail->next=pcur->next;
        NewTail=NewTail->next;
    }
    return NewHead;
}

只能说链表这部分的题空指针是绕不过去的槛，当然我也想直接将pcur跳到复制链表呢，但怎么说会出现对空指针解引用了，我只能说还是用原链表作载体可能对大部分题都是理想的？