【剑指offer】学习计划day2

素颜马尾好姑娘i 2024-04-25 20:05 60阅读 0赞

![58cf927ea4594661b369e61b53f6b896.png][]

**目录**

一. 前言

二.从尾到头打印链表

a.题目

b.题解分析

c.AC代码

三. 反转链表

a.题目

b.题解分析

c.AC代码

四. 复杂链表的复制

a.题目

b.题解分析

c.AC代码

--------------------

### 一. 前言 ###

> 本系列是针对Leetcode中剑指offer学习计划的记录与思路讲解。详情查看以下链接：
> 
> [剑指offer-学习计划https://leetcode.cn/study-plan/lcof/?progress=x56gvoct][offer-_https_leetcode.cn_study-plan_lcof_progress_x56gvoct]

本期是本系列的day2，今天的主题是----》链表（简单）

题目编号：JZ06，JZ24，JZ35

### 二.[从尾到头打印链表][Link 1] ###

#### a.题目 ####

![3ecf530380634a68a66f37ef235f7637.png][]

#### b.题解分析 ####

这题的方法有很多。**其一：**我们可以先遍历一遍链表，将节点的值放到一个数组中，最后将数组逆置即可。**其二：**我们可以使用一个辅助栈，利用栈后入先出的特性，将链表每个节点的值压入栈中，然后再依次出栈到数组即可。**其三：**利用递归，先走至链表末端，回溯时依次将节点值放入 数组返回即可。

#### c.AC代码 ####

//普通遍历
    int* reversePrint(struct ListNode* head, int* returnSize)
    {
    	int* ret=(int*)malloc(sizeof(int) * 10000);
    	int count = 0;
    	struct ListNode* cur = head;
        //将每个节点的值放入数组
    	while (cur)
    	{
    		ret[count++] = cur->val;
    		cur = cur->next;
    	}
    	int left = 0;
    	int right = count-1;
        //逆置数组
    	while (left < right)
    	{
    		int tmp = ret[left];
    		ret[left] = ret[right];
    		ret[right] = tmp;
    		left++;
    		right--;
    	}
    	*returnSize = count;
    	return ret;
    }

//递归法
    
    int ret[10000] = { 0 };//全局数组，用于存放逆序的链表
    int* reversePrint(struct ListNode* head, int* returnSize)
    {
    	if (head == NULL)//到链表尾，开始返回
    	{
    		*returnSize = 0;
    		return NULL;
    	}
    	reversePrint(head->next, returnSize);
    	ret[*returnSize] = head->val;
    	(*returnSize)++;
    	return ret;
    }

### 三. [反转链表][Link 2] ###

#### a.题目 ####

![776a1de48dc5426c86d91fd02a8a0d0c.png][]

#### b.题解分析 ####

本题我们在之前的单链表刷题篇有遇到过，当时我们采用了三种方法：**三指针法**、**头插法**和

**递归**。我们这里便不再细谈，不了解的小伙伴们可以跳转到往期：[【刷题篇】链表（上）![icon-default.png_t_N3I4][]http://t.csdn.cn/LcalP][icon-default.png_t_N3I4_http_t.csdn.cn_LcalP]

#### c.AC代码 ####

//三指针法
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* n1 = NULL;
        struct ListNode* n2 = head;
    
        while (n2)
        {
            struct ListNode* n3 = n2->next; //保存下一结点位置
            n2->next = n1;
            n1 = n2;
            n2 = n3;
        }
        //n2为空时，n1即为反转后表头
        return n1;
    }

//头插法
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* newhead = NULL; //新链表
        struct ListNode* first = head;
        while (first)
        {
            struct ListNode* next = first->next; //保存下一结点
            //进行头插
            first->next = newhead;
            newhead = first;
            first = next;
        }
        //全部结点头插完毕
        return newhead;
    
    }

//递归法
    struct ListNode* reverseList(struct ListNode* head) 
    {
        if (head == NULL || head->next == NULL) //当只有一个结点、没有结点、递归到最后一个结点时返回
            return head;
        struct ListNode* cur = reverseList(head->next); //找到链表尾结点
        head->next->next = head; //让下一结点指向当前结点
        head->next = NULL; //当前结点指向空
        return cur; //返回反转后头结点
    }

### 四. [复杂链表的复制][Link 3] ###

#### a.题目 ####

![c806bad24a744869a94c497a3a2daac8.png][]

#### b.题解分析 ####

本题要求我们对一个复杂链表进行一个深拷贝。假如这只是一个普通的单链表，那我们就可以一边遍历链表一边创建结点，当遍历结束时我们的复制也就完成了。但是这个链表除了有next指针指向下一个结点，还存在着一个随机指针random指向随机的结点。这就意味着当我们复制结点时random指向的结点我们可能还没有创建，如下图所示。所以我们需要变换思路。

![153826c1ebde430daa8d100b2ea9b6b7.gif][]

**法一：原地+结点拆分**

我们先遍历一遍链表，将每个结点进行复制后放入原结点的后面。然后再第二次遍历给复制的结点的random指针赋值，这样可以确保random指向的结点已经存在。最后再将链表中复制的结点进行拆分，形成一个新链表，返回即可。时间复杂度O(N)，空间复杂度O(1)

![e49d649044a649c69ca6890531a76a03.gif][]

**法二：哈希表**

我们也可以利用哈希表的查询功能来解题。先遍历一遍链表进行拷贝，每次拷贝结点时在哈希表中构建原结点和新结点的映射关系。然后根据原结点和新结点的映射关系再次遍历一遍链表给新结点的next指针和random指针进行赋值即可。时间复杂度O(N)，空间复杂度O(N)

![d3a4cbf7ca804bb393d5e5807f7d30f2.gif][]

####  **c.AC代码**  ####

//法1，原地+结点拆分
    
    class Solution
    {
    public:
        Node* copyRandomList(Node* head)
        {
            if (head == NULL)
            {
                return NULL;
            }
            //复制结点到当前结点后
            for (Node* cur = head; cur; cur=cur->next->next)
            {
                Node* pnode = new Node(cur->val);
                pnode->next = cur->next;
                cur->next = pnode;
            }
            //对复制的结点的random指针赋值
            for (Node* cur = head; cur; cur=cur->next->next)
            {
                if (cur->random)
                {
                    cur->next->random = cur->random->next;
                }
            }
    
            //每隔一项进行拆分
            Node* retNode = head->next;//指向新链表的头
            for (Node* cur = head; cur; )
            {
                Node* next = cur->next;
                if (next)
                {
                    cur->next = next->next;
                }
                cur = next;
            }
            return retNode;
    
        }
    };

//法2，哈希表
    
    class Solution
    {
    public:
        Node* copyRandomList(Node* head) 
        {
            unordered_map<Node*, Node*> value;//哈希表,建立索引
            value[NULL] = NULL;
            //第一次遍历建立索引映射
            for (Node* cur = head; cur; cur = cur->next)
            {
                value[cur] = new Node(cur->val);
            }
            //第二次遍历对新结点的指针进行赋值链接
            for (Node* cur = head; cur; cur = cur->next)
            {
                value[cur]->next = value[cur->next];
                value[cur]->random= value[cur->random];
            }
            return value[head]; 
        }
    };

--------------------

***以上，就是本期的全部内容啦*****?**

***制作不易，能否点个赞再走呢*****?**

[58cf927ea4594661b369e61b53f6b896.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/32aae7b3b49b455eadb91fc68a29630d.png
[offer-_https_leetcode.cn_study-plan_lcof_progress_x56gvoct]: https://leetcode.cn/study-plan/lcof/?progress=x56gvoct
[Link 1]: https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/?envType=study-plan&envId=lcof&plan=lcof&plan_progress=x96srfot
[3ecf530380634a68a66f37ef235f7637.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/bda874633dff4c4388b3d944c824a9e0.png
[Link 2]: https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=x930b8jj
[776a1de48dc5426c86d91fd02a8a0d0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0ffea4ab624a4fcd92780bdf086ebd36.png
[icon-default.png_t_N3I4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/5642ea033c1949d0b94540a7e2ff5fd2.png
[icon-default.png_t_N3I4_http_t.csdn.cn_LcalP]: http://t.csdn.cn/LcalP
[Link 3]: https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[c806bad24a744869a94c497a3a2daac8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/5b893d9eeb554020a1ce26ad6692f5ee.png
[153826c1ebde430daa8d100b2ea9b6b7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/b6daaddbdcc0418abfe22cd6189042a8.gif
[e49d649044a649c69ca6890531a76a03.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9dbdea7ee05c4278b35a422cf13b4180.gif
[d3a4cbf7ca804bb393d5e5807f7d30f2.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/70caf1c6258b4a479471a21c7b7cfc66.gif