C语言单链表OJ题(较难)

一、链表分割

牛客网链接

题目描述:

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

思路:

题目中要求不能改变原来的数据顺序,所以不能采用交换的方法写,应该单独创建两个链表,第一个链表尾插小于x的数据,另外一条链表尾插大于x的数据,最后将这两条链表进行链接。

尾插不改变原来数据顺序,头插将原来的数据顺序逆置

我们引用哨兵卫头结点解决这道题会更加方便。

不仅方便尾插,不需要分类判断空指针与否,而且也避免两个链表链接时第一个链表为空的情况。

TIP:

一般尾插时,最后一个结点的next容易出现问题,我们一般需要自己将其置成空指针

 代码:

#include <cstddef>
#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        struct ListNode* ghead,*gtail,*lhead,*ltail;
        //使用哨兵卫的头结点更加简单
        ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                ltail->next=cur;
                ltail=ltail->next;
            }
            else 
            {
                gtail->next=cur;
                gtail=gtail->next;
            }
            cur=cur->next;
        }
        gtail->next=NULL;//滞空,不然可能导致环形链表的出现
        ltail->next=ghead->next;
        struct ListNode* newhead=lhead->next;
        free(ghead);
        free(lhead);
        return newhead;
    }
};

二、链表的回文结构

牛客网链接

题目描述:

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:

1->2->2->1
返回:true

思路:

因为单链表只能从一个方向开始遍历,所以先让一串链表从中间结点开始往后逆置,接着两端链表进行比较。从中间结点开始逆置需要找中间结点,逆置也是之前讲过的,相当于再次复习巩固一遍

代码:

#include <cstddef>
class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        //寻找中间结点
        struct ListNode* fast=head;
        struct ListNode* slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        //从中间结点开始逆置
        struct ListNode* newhead=NULL;
        struct ListNode* cur=slow;
        struct ListNode* next=NULL;
        while(cur)
        {
            next=cur->next;
            cur->next=newhead;
            newhead=cur;
            cur=next;
        }
        //开始判断
        while(head && newhead)
        {
            if(head->val!=newhead->val)
            {
                return false;
            }
            head=head->next;
            newhead=newhead->next;
        }
        return true;
    }
};

三、相交链表

leetcode链接

题目描述:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

思路:

首先有一个暴力解法,从第一条链表开始,将每一个结点的地址与第二条链表比较,直到找到相同的为止,这样的时间复杂度就是O(N^2),不太理想,下面将一个O(N)的算法:

首先判断有无相交结点,直接遍历两条链表,看尾结点的地址是否相同。

如果相同,则计算两条链表的结点的差值,接着让长的链表先走差值步,这时因为相交结点后面的个数一定相同,长的链表走差值步后,相交结点的前面也是相同个数的结点,直接一一比较地址是否相同,就不用遍历两遍了,也就是O(N)

代码:

truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int numA=1;
    int numB=1;
    //判断是否有相交的结点
    while(curA->next)
    {
        curA=curA->next;
        numA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        numB++;
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int gap=abs(numA-numB);
    //直接假设长链表,不用if语句
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    if(numA<numB)
    {
        longlist=headB;
        shortlist=headA;
    }
    //长的先走差距步,走gap步就是后置--
    while(gap--)
    {
        longlist=longlist->next;
    }
    //在已知有公共结点的情况下,遍历返回
    while(1)
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
}

四、环形链表

leetcode链接

题目描述:

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

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

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

 思路:

本题要求较为简单,只需要判断是否含有环形结构,我们还是利用快慢指针的思想,快指针走两步,慢指针走一步,如果不带环,则快指针作为循环判断的条件,如果带环,则最后两者肯定会相遇,直到快慢指针地址相同时跳出循环

代码:

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

五、环形链表(进阶)

142. 环形链表 II - 力扣(LeetCode)

题目描述:

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

思路一:

本题主要找环形链表进入环的第一个节点,当然需要判断是不是环形链表,判断后需要进行一个数学的函数证明

 经过计算验证,我们发现一个指针从起点走,另外一个从相遇点走,在相同步伐下,他们会在入口点相遇

有这样一个等式,接下来就只需要找相遇点,正好上一题我们就找的是相遇点。

代码:

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* meet = NULL;
    struct ListNode* cur = head;
    //先判断是否有环
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //找到相遇结点
            meet = slow;
            break;
        }
    }
    if(meet==NULL)
    {
        return NULL;
    }
    //相遇节点与头结点一起走,直到相等,就是入口
    while(1)
    {
        if(meet==cur)
        {
            return meet;
        }
        meet=meet->next;
        cur=cur->next;
    }
}

思路二:

利用相交链表的思路。

首先也是找到相遇点,然后将相遇点的后面的结点断掉,这样就形成了两个链表,一条链表从头结点开始,另一条链表从断口开始。并且这两个链表的交点就是我们的入口点!

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* meet = NULL;
    struct ListNode* cur = head;
    //先判断是否有环
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //找到相遇结点
            meet = slow;
            break;
        }
    }
    if(meet==NULL)
    {
        return NULL;
    }
    //
    struct ListNode* newhead = meet->next;
    meet->next = NULL;
    struct ListNode* curnew = newhead;
    
    //开始相交链表
    int len1 = 0;
    int len2 = 0;
    while(curnew)
    {
        curnew=curnew->next;
        len1++;
    }
    while(cur)
    {
        cur=cur->next;
        len2++;
    }
    int gap=abs(len1-len2);
    struct ListNode* longlist = newhead;
    struct ListNode* shortlist = head;
    if(len1<len2)
    {
        longlist = head;
        shortlist=newhead;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(1)
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    
}

六、复制带随机值指针的链表

138. 复制带随机指针的链表 - 力扣(LeetCode)

题目描述:

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码  接受原链表的头节点 head 作为传入参数。

思路:

本题要求拷贝一串链表,并且结点中含有随机值指向,并且要求拷贝的链表与原链表一样,随机域也要指向一样。

  1. 首先,我们将拷贝的结点一个一个插在原结点后面
  2. 这时拷贝结点的随机指针域就是原结点指向的随机指针域的next.
  3. 再取拷贝结点组成新的链表

代码:

struct Node* copyRandomList(struct Node* head) 
{
    struct Node* copy = NULL;
    struct Node* next = NULL;
    struct Node* cur = head;
    while(cur)
    {
        //copy结点放在原结点后面
        next = cur->next;
        copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        cur->next = copy;
        copy->next = next;
        cur = copy->next;
    }
    //拷贝随机指针
    cur = head;
    while(cur)
    {
        copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {   
            //关键
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    cur = head;
    while(cur)
    {
        //将copy组装成一个新链表(尾插)
        copy = cur->next;
        if(copyhead == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            //尾插
            copytail->next = copy;
            copytail = copytail->next;
        }
        //恢复原链表
        cur->next = copy->next;
        cur = cur->next;
    }
    return copyhead;
}