正文

leetcode剑指offer学习计划第二天题目(代码片段)

桃浪十七丶  桃浪十七丶  2022-12-03  521

关键词：

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入： head = [1,3,2] 输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

所给代码如下

/**
 1. Definition for singly-linked list.
 2. struct ListNode 
 3.     int val;
 4.     ListNode *next;
 5.     ListNode(int x) : val(x), next(NULL) 
 6. ;
 */
class Solution 
public:
    vector<int> reversePrint(ListNode* head) 

    
;

思考：

要把链表元素逆序打印，我现在可以想到实现逆序的有

可以数组从尾到头逆序打印
可以链表逆置再打印
可以用出栈入栈的性质来实现逆序

这题目的标签是栈，数组，链表，双指针，也就是说用栈就行，双指针现在也没有做过相关题目，如果以后接触到了可以回头再考虑这个题目。
画个草图来辅助做题：

步骤已经很明确了，遍历链表元素并且入栈，然后出栈直到栈空。
用代码实现

class Solution 
public:
    vector<int> reversePrint(ListNode* head) 
		vector<int> arr;
		stack<int> newStack;
		ListNode* tmp = head;
		while(tmp != nullptr) 
			newStack.push(tmp->val);
			tmp = tmp->next;
		
		while(!newStack.empty()) 
			arr.push_back(newStack->top());
			newStack.pop();
		
		return arr;
    
;

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

题目给出代码框架：

/**
 1. Definition for singly-linked list.
 2. struct ListNode 
 3.     int val;
 4.     ListNode *next;
 5.     ListNode(int x) : val(x), next(NULL) 
 6. ;
 */
class Solution 
public:
    ListNode* reverseList(ListNode* head) 

    
;

思考：

这个题目其实和基本的链表操作没有差多少

先构造两个结点，pre指向空，current指向head
再按照以往的操作基本向后遍历即可

答案

class Solution 
public:
    ListNode* reverseList(ListNode* head) 
        ListNode* currentNode = head;
		ListNode* pre = nullptr;
		while(currentNode != nullptr) 
			ListNode* tmpNode = currentNode->next;	// 这是下次移动的位置
			currentNode->next = pre; // 把current指向原来next的指针指向pre
			pre = currentNode;	// pre向后移动到原来current的位置
			currentNode = tmpNode;	// current向后移到了原来tmp的位置
		
		return pre;
    
;

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

题目给代码框架：

/*
// Definition for a Node.
class Node 
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) 
        val = _val;
        next = NULL;
        random = NULL;
    
;
*/
class Solution 
public:
    Node* copyRandomList(Node* head) 
        
    
;

思考：

看到这个题目，首先会想到可以把random随即节点和next节点分开处理
这个题目的标签是链表和哈希，但是比较熟悉的是链表操作，比较菜的水平就用菜的方法，直接上链表，搞细胞分裂了
细胞分裂是先复制材料再分裂，这个题目也一样，处理next节点和普通的链表插入操作一样
创建新节点cpNode，把当前节点的值传给cpNode，然后从头到尾遍历插入即可完成next的复制工作
然后处理random，在做这个题目的时候也是不太能理解要怎么写这个代码，还是要感谢一位学长画这个图给我看，瞬间就明白了其实lc官方给的图可以简化成这样来辅助理解
细胞分裂材料复制完毕后完就可以进行分裂了。把复制体分开即可

答案

class Solution 
public:
    Node* copyRandomList(Node* head) 
		if(head == nullptr) 
			return nullptr;
		
		// 复制next
		Node* tempNode = head;
		while(tempNode != nullptr) 
			Node* cpNode = new Node(tempNode->val);
			cpNode->next = tempNode->next;
			tempNode->next = cpNode;
			tempNode = cpNode->next;
		
		
		// 复制random
		tempNode = head;
		while(tempNode != nullptr) 
			if(tempNode->random != nullptr) 
				tempNode->next->random = tempNode->random->next;	//正如思考5里画的那样
			
			tempNode = tempNode->next->next;
		
		
		// 开始细胞分裂
		tempNode = head->next;
		Node* pre = head;
		Node* cpHead = head->next;
		while(tempNode->next != nullptr) 
			pre->next = pre->next->next;
			tempNode->next = tempNode->next->next;
			pre = pre->next;
			tempNode = tempNode->next;
		
		pre->next = nullptr;
		return cpHead;
	
;

leetcode剑指offer学习计划第一天题目(代码片段)

题目：剑指Offer09.用两个栈实现队列用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead操... 查看详情

leetcode剑指offer学习计划第一天题目(代码片段)

leetcode-学习计划之剑指offer(代码片段)

剑指Offer30.包含min函数的栈力扣，定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数在该栈中，调用min、push及pop的时间复杂度都是O(1)。示例:MinStackminStack=newMinStack();minStack.push(-2);minStack.push(... 查看详情

leetcode-学习计划之剑指offer(代码片段)

《剑指offer》算法题第二天

今日题目（分别对应剑指书3~9题）：数组中重复的数字二维数组中的查找替换空格从尾到头打印链表重建二叉树二叉树的下一个节点用两个栈实现队列今日重点为1,2,5,6，后面会有详细的思路解析，现在先来简单地提一下其他题... 查看详情

leetcode（剑指offer）-22.链表中倒数第k个节点(代码片段)

题目链接：点击打开链接题目大意：略解题思路：略相关企业字节跳动AC代码Java/***Definitionforsingly-linkedlist.*publicclassListNode*intval;*ListNodenext;*ListNode(intx)val=x;**///解决方案(1)classSolutionpublicListNod 查看详情

leetcode（剑指offer）-22.链表中倒数第k个节点(代码片段)

leetcode（剑指offer）-50.第一个只出现一次的字符(代码片段)

题目链接：点击打开链接题目大意：略解题思路：略相关企业字节跳动AC代码Java//解决方案(1)classSolutionpubliccharfirstUniqChar(Strings)HashMap<Character,Boolean>dic=newHashMap<>();char[]sc=s.toCharArra 查看详情

leetcode（剑指offer）-50.第一个只出现一次的字符(代码片段)

leetcode（剑指offer）-52.两个链表的第一个公共节点(代码片段)

题目链接：点击打开链接题目大意：略解题思路：主要能想到各组走完自己的链路+再走对方的链路一定能碰到在第一个相交点相关企业优步（Uber）腾讯（Tencent）PayPal谷歌（Google）三星高盛... 查看详情

leetcode（剑指offer）-52.两个链表的第一个公共节点(代码片段)

剑指offer（第2版）完整题解笔记&c++代码实现（leetcode版）(代码片段)

文章目录原书目录剑指Offer03. 数组中重复的数字剑指Offer04. 二维数组中的查找剑指Offer05. 替换空格剑指Offer06. 从尾到头打印链表剑指Offer07. 重建二叉树剑指Offer09. 用两个栈实现队列剑指Offer10-I. 斐波那契数列剑指Offer10-II. ... 查看详情

剑指offer（第2版）完整题解笔记&c++代码实现（leetcode版）(代码片段)

学习笔记leetcode剑指offer35.复杂链表的复制(代码片段)

题目：请实现copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。迭代+节点拆分法/*//DefinitionforaNode.classNodepubli... 查看详情

学习笔记leetcode剑指offer35.复杂链表的复制(代码片段)

⭐算法入门⭐《堆》简单02——leetcode剑指offer40.最小的k个数(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述给你一个大小为m×nm\\timesnm×n的矩阵mat，矩阵由若干军人和平... 查看详情

leetcode训练剑指offer（专项突击）——双指针全刷(代码片段)

目录[剑指OfferII006.排序数组中两个数字之和](https://leetcode-cn.com/problems/kLl5u1/)——简单题目描述：题解方法一：数组已经排序了，直接首尾双指针；[剑指OfferII007.数组中和为0的三个数](https://leetcode-cn.com/problems/1fGaJU... 查看详情

剑指offer题目系列一

本篇介绍《剑指offer》第二版中的四个题目：找出数组中重复的数字、二维数组中的查找、替换字符串中的空格、计算斐波那契数列第n项。这些题目并非严格按照书中的顺序展示的，而是按自... 查看详情