当前位置： 首页 > article >正文

数据结构_第五关：单链表OJ题练习

article 2024/12/23 5:54:56

OJ题题目简介和链接：

1.删除链表中等于给定值 val 的所有结点。OJ题链接

2.反转一个单链表。OJ题链接

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ题链接

4.. 输入一个链表，输出该链表中倒数第k个结点。OJ题链接

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ题链接

7.链表的回文结构。OJ链接

8.输入两个链表，找出它们的第一个公共结点。OJ题链接

9.给定一个链表，判断链表中是否有环。OJ题链接

10.给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL。OJ题链接

11.给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。OJ题链接

目录

OJ题题目简介和链接：

1.移除链表元素

2.反转一个单链表

3.链表的中间结点

4.链表中倒数第k个结点

 5.合并两个有序链表

 6.链表分割

 7.链表的回文

8.相交链表

9.环形链表，判断是否有环

10.环形链表2，如果有环，返回入环点

 11.复制带随机指针的链表

1.移除链表元素

思路：

  1. 先判度链表是否为NULL
  2. 定义一个新的头结点newhead（保存头结点地址用），再定义一个尾结点tail（进行插入用），刚开始置为空，
    就是让新的头结点，尾插，源链表不是val的值
  3. 判断cur->val是否等于val，
    不等于，再判断这是不是第一个结点，
    如果是第一个结点，那此时，说明第一个结点的值不是val，可以插入
    让newhead和tail=cur
  4. 如果不是第一个结点，则用tail进行尾插，tail->next=cur;  tail=tail->next;
  5. 如果cur->val的值等于val，则利用temp将该值free掉，并继续往后走
  6. 重复3，4，5，直到cur的值为NULL
  7. 最后给新的链表的尾加上NULL即可

代码：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //判断链表是否为空
    if(head==NULL)
           return NULL;

    struct ListNode*cur=head;

    //定义新一个的链表
    struct ListNode*newhead=NULL;//newhead用来保存新链表的头节点地址
    struct ListNode*tail=NULL;//tail用来往新链表里面插入
    while(cur)
    {
        if(cur->val!=val)//判断原链表的值是否是val
        {
            if(tail==NULL)//判断是不是新链表的第一个结点，头节点的值不是val可以往新链表里面插入
            {
                newhead=tail=cur;
            }
            else//不是新链表的第一个结点，直接头插
            {
                tail->next=cur;
                tail=tail->next;
            }
            cur=cur->next;
        }
        else//原链表的值等于val的时候进行跳过处理
        {
            struct ListNode*tmp=cur->next;
            free(cur);
            cur=tmp;
        }
    }
    if(tail)
        tail->next=NULL;
    return newhead;
}

2.反转一个单链表

 思路1：

  • 和上面的方法一样，创建一个新的链表，将原链表的值头插进新的链表，并返回即可

代码：

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode*newhead=NULL;//创建新的链表
    struct ListNode*tmp=NULL;//记录cur的next
    struct ListNode*cur=head;
    while(cur)
    {
        tmp=cur->next;
        //头插
        cur->next=newhead;
        newhead=cur;
        cur=tmp;
    }
    return newhead;
}

 思路2：

  • 用1指向空，2指向1...
  • 需要用三个指针进行操作
  • 用n1和n2进行指向的转换，n3记录下一个结点地址

 

代码：

struct ListNode* reverseList(struct ListNode* head)
{
   if(head==NULL)
    return NULL;
    struct ListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=n2->next;
    while(n2)
    {
        n2->next=n1;

        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}

3.链表的中间结点

 思路：

  • 利用快慢指针，快指针每次走两步，满指针每次走一步，当快指针走到头时，满指针刚好走到中间
  • 这里要分两种情况：单链表为奇数和单链表为偶数，
    奇数时，快指针走到最后一个结点处，慢指针走到中间
    偶数时，快指针走到NULL处，满指针走到中间的下一个

代码：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        struct ListNode*slow,*fast;
        fast=slow=head;
        
        //因为不知道链表时奇数还是偶数，所以用fast&&fast->next来判断
        while(fast && fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
};

4.链表中倒数第k个结点

 思路：

  • 快慢指针，可以先让快指针走k个结点，然后快指针和慢指针一起走

  • 根据示例可以看到第三组，第四组的k都比数组大，所以应该加上一个判断，判断快指针走了K个结点后是否为空

代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
		struct ListNode* fast,* slow;
		fast = slow = pListHead;
		while(k--)
		{
			if(fast==NULL)
				return NULL;
			fast=fast->next;
		}
		while(fast)
		{
			fast = fast->next;
			slow = slow->next;
		}
		return slow;
    }
};

 5.合并两个有序链表

 

思路：

创建一个新的链表，然后对原来的链表进行对比，数据小的，尾插进新的链表里面

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	//判断链表是否为空
	if(list1==NULL)
			return list2;
	if(list2==NULL)
			return list1;
	if(list1==NULL || list2==NULL)
			return NULL;
	
	//定义新的头来记录两个链表里面的数据
	struct ListNode*newhead=NULL,*tail=NULL;
	struct ListNode*cur1=list1,*cur2=list2;
	struct ListNode*n1=cur1->next,*n2=cur2->next;

	//确定新的链表的头是哪个
	if(cur1->val <= cur2->val)
	{
		tail = cur1;
		newhead = tail;
		cur1 = n1;
		if(cur1 != NULL)
			n1 = n1->next;
	}
	else
	{
		tail = cur2;
		newhead = tail;
		cur2 = n2;
		if(cur2 != NULL)
			n2 = n2->next;
	}

	//进行循环比较，当一个链表为空的时候退出循环
	while(cur1 && cur2)
	{
		if (cur1->val <= cur2->val)
		{
			tail->next = cur1;
			tail = tail->next;
			cur1 = n1;
			if (cur1 != NULL)
				n1 = n1->next;
		}
		else
		{
			tail->next = cur2;
			tail = tail->next;
			cur2 = n2;
			if (cur2 != NULL)
				n2 = n2->next;
		}
	}

	//判断哪个链表是空，然后将不是空的链表链接的新链表后面
	if (cur1 == NULL)
	{
		while (cur2)
		{
			tail->next = cur2;
			tail = tail->next;
			cur2 = n2;
			if (cur2 != NULL)
				n2 = n2->next;
		}
	}
	else
	{
		while (cur1)
		{
			tail->next = cur1;
			tail = tail->next;
			cur1 = n1;
			if (cur1 != NULL)
				n1 = n1->next;
		}
	}
	return newhead;
}

 6.链表分割

 比如：

 思路：

  • 加上哨兵位的头节点进行处理
  • 注意：要让greaterHead的最后一个数指向NULL不然会发生死循环

 代码：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        //定义四个变量，less里面放小于x的数，greater里面放大于x的数
        //Head里面存放该链表的头结点地址，Tail进行判断和插入
        struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
        //为这两个链表开辟一个哨兵位的头结点
        lessHead=lessTail = (struct ListNode*)malloc(sizeof(struct listNode));
        greaterHead=greaterTail = (struct ListNode*)malloc(sizeof(struct listNode));
        
        lessTail->next = greaterTail->next = NULL;
        
        struct listNode* cur = pHead;
        while(cur)//当cur为空时结束
        {
            if(cur->val < x)//小于x的尾插list链表里面
            {
                lessTail->next=cur;
                lessTail=lessTail->next;
            }
            else 
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            cur = cur->next;
        }
        //让小的链表尾的next指向大的链表的哨兵位头节点的next
        lessTail->next=greaterHead->next;
        //大数组的尾置空，以防止生成环
        greaterTail->next=NULL;
        //用phead指向lessHead的next完成
        pHead=lessHead->next;
        //最后释放两个哨兵头结点
        free(lessHead);
        free(greaterHead);

        return pHead;
        
    }
};

 7.链表的回文

 思路：

  • 回文就是两边对称
  • 反转后半段，然后和前半段进行比较
  • 借助之前的快慢指针找到中间节点，然后再进行头插反转
  • 如果时偶数，直接进行判断就行，
  • 如果是奇数，因为没有改变2的next，所以2的next还是3，依然可以进行判断，走到NULL结束即可

代码：

class PalindromeList {
public:
    //找出链表的中点
    struct ListNode* middleNode(ListNode* head) 
    {
        struct ListNode*slow,*fast;
        fast=slow=head;
        
        while(fast && fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    //将链表反转
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode*newhead=NULL;//创建新的链表
        struct ListNode*tmp=NULL;//记录cur的next
        struct ListNode*cur=head;
        while(cur)
        {
            tmp=cur->next;
            //头插
            cur->next=newhead;
            newhead=cur;
            cur=tmp;
        }
        return newhead;
    }
    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode*mid=middleNode(A);
        struct ListNode*rhead=reverseList(mid);
        //不知到链表是奇数还是偶数就两个链表的结束条件一起判断
        while(A && rhead)
        {
            if(A->val!=rhead->val)
                return false;
            A=A->next;
            rhead=rhead->next;
        }
        return true;
    }
};

8.相交链表

难点：

  • 单链表，两个数组长度不同，要判断是否相交和找出相交结点 

思路：

  • 还是利用快慢指针，先算出两个数组的大小，相减差值的绝对值就是，快指针需要多走的结点
  • 要计算处数组的大小，就需要遍历数组，同时也能找到尾结点，如果尾结点不相同
    则说明这两个链表不相交，返回NULL
  • 尾结点数相同就相交，尾结点不同就返回NULL，所以我们可以直接找尾直接用
    while（cur->next）判断，之后如果有空链表，再前面加一步判断即可
  • 否则，在快指针走了差值步之后，快慢指针一起走，直到两个指针相等时，就是这两个链表的交点位置

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*A=headA,*B=headB;
    int lenA=0,lenB=0;
    
    //找尾，计算每个链表的大小
    while(A->next)
    {
        lenA++;
        A=A->next;
    }
    while(B->next)
    {
        lenB++;
        B=B->next;
    }

    //尾结点不相等就不相交
    if(A!=B)
    {
        return NULL;
    }
    
    //计算差值，并找出长链表和短链表
    int gap=abs(lenA-lenB);
    struct ListNode*longlist = headA,*shortlist = headB;
    if(lenB>lenA)
    {
        longlist=headB;
        shortlist=headA;
    }

    //长链表走gap步
    while(gap--)
    {
        longlist=longlist->next;
    }

    //同时走，找交点
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }

    return longlist;
}

9.环形链表，判断是否有环

 思路：

  • 快慢指针，fast走两步，slow走一步

  • 当slow也走进环里面的时候，这是就会形成一个fast追slow的追击问题

  • 只要fast和slow差一步，并且是个环，就一定会相遇

bool hasCycle(struct ListNode *head) {
    struct ListNode*fast=head,*slow=head;
    //这里也要判断fast->next是因为如果链表只有一个数，没有fast->next->next，就会出错
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
            return true;
    }
    return false;
}

10.环形链表2，如果有环，返回入环点

 这个题主要是一个智力题，对代码能力的要求不大，主要是看你能不能想明白其中的道理

这里先说结果：

再相遇的时候，指针head重新从头走，指针meet从环的相遇点处走，

在head与meet相遇的时候，这个点就是环的入口点

解释：

  •  所以在圈很大的时候（特殊情况），走的距离：慢指针=L+N，快指针=L+N+C
  • 由快指针是满指针走的距离的2倍可以得到：2*（L+N）=L+N+C，C=L+N，可得出结论
  • 但是这只是一个特殊情况，不足以证明环小的时候
  • 应该为：

 代码如下：

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode*fast=head,*slow=head;
    //这里也要判断fast->next是因为如果链表只有一个数，没有fast->next->next，就会出错
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            struct ListNode*meet =slow;
            //让头结点和meet一起走，找到他们相交的点
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

 11.复制带随机指针的链表

 

思路1：

  • 可以利用相对位置求解，我们要找random指向的是第几个结点

  • 就比如，先对7这个结点的random进行复制，就对数组进行一次遍历，遍历过程中记录num，该结点是第几个结点，当random指向的地址和遍历到的地址位置相同时，就返回num的值

  • 在进行复制random的时候，就直接利用相对位置num进行复制

  • 但是这样的话，得到的时间复杂度是O(n^2)

如果要求时间复杂度是O(n)的话，要怎么做？

思路2：

1.拷贝结点链接在源节点的后面：

 2.设置拷贝结点的random

 拷贝结点的random=cur的random的next

 3.拷贝结点解下来，连接组成拷贝链表

 

代码（思路2的实现）：

struct Node* copyRandomList(struct Node* head) 
{
    //1.拷贝结点链接到源节点的后面
    struct Node* cur=head;
    while(cur)
    {
        struct Node* Next=cur->next;
        //创建新的结点空间
        struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
        //让新的结点的值=源结点的值
        copy->val=cur->val;
        
        //将新节点插入到源节点的后面
        cur->next=copy;
        copy->next=Next;

        cur=Next;
    }

    //2.将源结点的random进行复制
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }

    //3.将copy的在源节点后面的结点解下来放到一起
    cur=head;
    struct Node*CopyHead=NULL,*tail=NULL;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*Next=copy->next;
        cur->next=Next;
        
        //尾插
        if(CopyHead==NULL)
        {
            CopyHead=tail=copy;
        }
        else
        {
            tail->next=copy;
            tail=tail->next;
        }
        cur=Next;
    }
    return CopyHead;
}


http://www.kler.cn/a/6572.html

相关文章：

  • electron打包linux环境
  • 电商数据流通的未来：API接口的智能化与自动化趋势
  • Go 语言常量
  • 【Rust自学】4.4. 引用与借用
  • Apache Solr RCE(CVE-2017-12629)--vulhub
  • [Unity] 【VR】【游戏开发】在VR中使用New Input System获取按键值的完整教程
  • 反射学习总结
  • ABC296E Transition Game
  • c++实现sqlite的增删改查
  • 如何下载ChatGPT-ChatGPT如何写作
  • 中华好诗词（六）
  • ChatGPT 从注册到自建应用
  • Linux【环境变量】
  • Apple Pencil性价比高吗？第三方平替电容笔排名
  • 你好快哦, HikariCP
  • 获取QTableWidget中某个单元格的坐标
  • 互联网摸鱼日报（2023-04-06）
  • 日益强大的人工智能OpenAI ChatGPT GPT-4真的会让程序员失业吗？
  • “卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解
  • 「读书感悟系列」失明症漫记
  • 蓝桥杯赛前冲刺-双指针和图论专题（包含历年蓝桥杯真题和详细注释代码）
  • 【GPT4】微软 GPT-4 测试报告（9）结论与展望
  • 苹果手机配什么无线蓝牙耳机好？适配苹果手机的蓝牙耳机推荐
  • 网络系统集成实验（三）| 系统集成虚拟局域网（VLAN）配置
  • abaqus子程序vumat安装使用
  • 2022蓝桥杯省赛——砍竹子