【算法与数据结构】链表——题目详解网站首页 技术交流

【算法与数据结构】链表——题目详解

LAWKAWAI 2024-06-14 17:17:53

简介【算法与数据结构】链表——题目详解

题目详解

Leetcode-206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

在这里插入图片描述
输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题目解析-1：链表头插法

用一个指针遍历链表，把每次遍历到的节点都插入到一个新的链表的头部

// Definition for singly-linked list.
#include <stdio.h>
#include <stdlib.h>

 struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };




class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		ListNode new_head, *p = head, *q;   // q用来记录当前节点的下一个节点. newhead是虚拟头节点
		new_head.next = NULL;               // 新的链表头部
		while (p)
		{
			q = p->next;                     // 先记录一下原链表当前节点p的下一个节点
			p->next = new_head.next;         // 将当前节点插入到新链表的第一个节点
			new_head.next = p;
			p = q;                          // 当前节点再次回到原链表的下一个节点
		}
		return new_head.next;               // 返回新链表的虚拟头节点的下一个节点


	}
};

测试结果：

在这里插入图片描述

题目解析-2：递归

假设后面部分已经反转了，head应该接在哪里？
head节点应该接在head的下一个节点的后面。
递归过程： 如果没有到达边界条件，首先先记录一下当前head节点的下一个节点，利用递归函数，将后面部分的全部反转掉，反转之后将head接在刚才记录的节点的后面

重要： 给【递归函数】一个明确的语义：翻转当前链表
实现边界条件时的程序逻辑：空链表和只有一个节点的链表
假设递归函数调用返回结果是正确的，实现本层函数逻辑： f(n) = (f(n-1),1)


// Definition for singly-linked list.
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};




class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (head == NULL || head->next == NULL) return head;

		ListNode *tail = head->next;   // 先记录一下head的下一个节点
		ListNode *new_head = reverseList(head->next);       // 将head后面的部分反转
		head->next = tail->next;   // 把head的下一个节点接在空指针,因为反转后的tail的下一个节点为空指针
		tail->next = head;     // 把head接在反转后的尾节点后面

		return new_head;


	}
};

Leetcode-141.环形链表

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

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

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

示例 1：

在这里插入图片描述
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

在这里插入图片描述
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

在这里插入图片描述

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个有效索引。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

题目解析：快慢指针

想象一个跑道，跑的快的人肯定可以套跑的慢的人一圈；
如果是直道，100米直道，跑的快的更快碰到终点。
设置两个指针，一个快指针，一个慢指针
如果有环：快指针会赶上慢指针，快指针和慢指针相等
如果没有环：快指针会先到达空指针


// Definition for singly-linked list.
#include <stdio.h>
#include <stdlib.h>


 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
	bool hasCycle(ListNode *head) {
		ListNode *p = head, *q = head;  // p是慢指针，q是快指针
		while (q && q->next)
		{
			p = p->next;   // p每次往后跑一步
			q = q->next->next;
			if (p == q) return true;   // 如果赶上了，证明有环
		}

		return false;
	}
};

测试结果

在这里插入图片描述

Leetcode-202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

1 <= n <= 231 - 1

题目解析：链表法

当前数字变换到下一个数字的过程，与链表结构的对应箭头关系对应：19->82->68->100->1
符合链表的特征
1当成链表中的空地址
问题变成：从19（头节点）开始，是否可以到达1（空地址）
也就是要判断这个链表是否有环，如果有环，则不是快乐数；如果没环，则是快乐数

所以数据结构不仅是真实的数据结构，更重要是其蕴含的内在的逻辑结构

class Solution {
public:
	bool isHappy(int n) {
		int p = n, q = n;  // p是慢， q是快
		while (q != 1)
		{
			p = getNext(p);  // p每次走一步
			q = getNext(getNext(q));   // q每次走两步
			if (p == q && p != 1) return false;  // p还不能等于1， 因为如果p=1， 那么往后走多少步都是1，这样q肯定能赶上p，会判断有环，即不是快乐数
			                                     // 举例：n = 10, p = 1, q = 1, p == q为真，那么判断有环，但实际是没有环的，所以要把p=1剔除
		}
		return true;

	}

	int getNext(int x)
	{
		int len = 0;
		while (x)
		{
			len += (x % 10) * (x % 10);
			x /= 10;
		}
		return len;
	}
};

Leetcode-61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

在这里插入图片描述
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

在这里插入图片描述
输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

题目解析：双指针等距移动法

第一步处理：由于k值可能超过链表的长度，所以先用k值对链表的长度取余，余数才是真正要移动的个数

一开始，p和q两个指针，p指向最后的空地址，q指向倒数第k-1个节点，那么此时p指针和q指针之间相差k+1个节点的距离。
此时再向前移动q指针到头节点，同步地p指针也保持相同距离往前移动，那么p所指向的节点就是距离头节点k+1个节点的距离
所以，一开始让p指针指向距离头节点k+1距离的节点，q指向头节点，然后让两个指针同步向后移动，直到p指针碰到空地址，此时q指针指向了要断开的地方的前一位。然后可以实行旋转操作

旋转操作：先让p指针回到要断开的地方，p = q->next；然后将q->next指向空地址；最后将p开始的小链表的最后一个节点指向头节点。


//  Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
	int getLength(ListNode *head)
	{
		int n = 0;
		for (ListNode *p = head; p; p = p->next) n += 1;
		return n;
	}
	ListNode* rotateRight(ListNode* head, int k) {
		if (head == nullptr) return head;
		int n = getLength(head);   // 获取链表的长度
		k %= n;                    // k对n取余
		if (k == 0) return head;
		ListNode *p = head, *q = head;
		for (int i = 0; i <= k; i++) p = p->next;   // 让p指针向后走k+1步
		while (p)
		{
			p = p->next;
			q = q->next;
		}
		// 此时p走到了空地址，q也走到可以断开链表的位置
		
		p = q->next;  // 回到断开的地方
		q->next = nullptr;
		// 可以使用q来遍历p后的链表
		q = p;
		while (q->next) q = q->next;
		q->next = head;

		return p;

	}
};

测试结果

在这里插入图片描述

题目解析：移1法

每次移动一个节点到头节点处，循环k次


//  Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
	int getLength(ListNode *head)
	{
		int n = 0;
		for (ListNode *p = head; p; p = p->next) n += 1;
		return n;
	}

	ListNode * moveOne(ListNode *head, int n)
	{
		ListNode *q = head, *p = head;
		for (int i = 0; i < n - 1; i++) p = p->next;     // p指向最后一个节点
		for (int i = 0; i < n - 2; i++) q = q->next;  // q指向倒数第二个节点
		q->next = nullptr;
		p->next = head;

		return p;


	}


	ListNode* rotateRight(ListNode* head, int k) {
		if (head == nullptr) return head;
		int n = getLength(head);   // 获取链表的长度
		k %= n;                    // k对n取余
		if (k == 0) return head;

		for (int i = 0; i < k; i++) head = moveOne(head, n);  // 每次只移动一个节点，移动k次


		return head;

	}
};

Leetcode-19. 删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

在这里插入图片描述

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题目解析：双指针等距移动法

关键：找到倒数第n+1个节点
技巧：当要删除倒数第n个节点，也就是头节点，那使用双指针的q指向哪个节点？所以这里需要使用虚拟头节点，将无头链表变成有头链表
删除操作：先将p指针向后移动n+1位，然后同时移动p和q指针，直到p碰到空地址，删除q的下一个节点即可


struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};





class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		ListNode newhead, *p = &newhead;
		newhead.next = head;   // 虚拟头节点

		ListNode *q = p;
		for (int i = 0; i <= n; i++) p = p->next;  // p移动n+1
		while (p)
		{
			p = p->next;
			q = q->next;
		}
		q->next = q->next->next;

		return newhead.next;

	}
};

测试结果

在这里插入图片描述

Leetcode-142. 环形链表II

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

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

不允许修改链表。

示例 1：

在这里插入图片描述
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

在这里插入图片描述
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

在这里插入图片描述
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：

你是否可以使用 O(1) 空间解决此题？

题目解析：快慢指针

p是慢指针，q是快指针
假设环的前面的长度为a，当慢指针p走到交点处，q应该走到2a处，此时q和p同时在环里
经过多少轮，快指针能够追上慢指针？
由于每轮快指针都能追上一步慢指针，假设环的长度为x，只剩下x-a轮就能追上慢指针；
当快指针追上慢指针，慢指针走了x-a步
那么，快指针和慢指针相遇的地方，距离交点a的长度；而链表头节点距离环的起点也是a
此时找到了两个不同的点，距离环的起点都为a
此时把其中的一个指针设置回链表头节点，然后，p和q再一起往后走，当他们相遇的地方，就是环的起始点
在这里插入图片描述



struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		ListNode *p = head, *q = head;   

		while (q && q->next)
		{
			p = p->next;
			q = q->next->next;
			if (p == q) break;
		}
		// 此时p和q在环中相遇或者q为空地址或者q的下一个节点为空地址
		if (q == nullptr || q->next == nullptr) return nullptr;
		// 将其中一个指针置为头节点
		p = head;
		while (p != q) p = p->next, q = q->next;  // 重新出发，直到再次碰到，此时的指针指向环的开始

		return p;
	}
};

测试结果

在这里插入图片描述

Leetcode-92. 反转链表II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：

在这里插入图片描述
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶：

你可以使用一趟扫描完成反转吗？

题目解析：递归法

如果只看要反转的链表，相当于要反转一个普通的链表
大问题：反转链表的[left, right]
子问题：反转链表的[1, right - left + 1]
子问题：反转链表的[1, right - left ]
…
子问题：反转[1, 1]的链表，这个就不用反转了，就是边界条件

算法过程：

当前节点head还没递归到反转区域（left != 1），递归函数reverseBetween(head->next, left - 1, right - 1)得到反转后的链表，接到head当前节点的后面
当前节点head递归到反转区域(left = 1)，递归函数reverseBetween(head->next, left, right - 1)得到反转后的链表，将head节点插入到反转区域的尾节点的后面


struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
	ListNode* reverseBetween(ListNode* head, int left, int right) {

		if (left == 1 && right == 1) return head;

		if (left != 1)   // 还没递归到待反转的区域
		{
			head->next = reverseBetween(head->next, left - 1, right - 1);
		}
		else { 
			ListNode *tail = head->next;   // 先记录反转后的尾节点，也就是当前节点的下一个节点
			ListNode *new_head;            // 反转完以后的头节点的地址
			new_head = reverseBetween(head->next, left, right - 1);   // 完成后半部分的反转
			// 将原来的头节点插入到反转区域的尾节点的后面
			head->next = tail->next;
			tail->next = head;
			head = new_head;
		}

		return head;
	}
};

测试结果

在这里插入图片描述

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-linked-list-ii

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
《LeetCode》—— 哈希

下一篇
C#--使用Quartz实现定时任务

站长推荐

SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
Unity创建文本时自动修改默认字体
Unity创建文本时自动修改默认字体

您现在的位置是：首页 >技术交流 >【算法与数据结构】链表——题目详解网站首页技术交流

【算法与数据结构】链表——题目详解

题目详解

Leetcode-206. 反转链表

示例 1：

示例 2：

示例 3：

提示：

进阶：

题目解析-1：链表头插法

测试结果：

题目解析-2：递归

Leetcode-141.环形链表

示例 1：

示例 2：

示例 3：

提示：

进阶：

题目解析：快慢指针

测试结果

Leetcode-202. 快乐数

示例 1：

示例 2：

提示：

题目解析：链表法

Leetcode-61. 旋转链表

示例 1：

示例 2：

提示：

题目解析：双指针等距移动法

测试结果

题目解析：移1法

Leetcode-19. 删除链表的倒数第N个节点

示例 1：

示例 2：

示例 3：

提示：

题目解析：双指针等距移动法

测试结果

Leetcode-142. 环形链表II

示例 1：

示例 2：

示例 3：

提示：

进阶：

题目解析：快慢指针

测试结果

Leetcode-92. 反转链表II

示例 1：

示例 2：

提示：

进阶：

题目解析：递归法

测试结果

上一篇 《LeetCode》—— 哈希

下一篇 C#--使用Quartz实现定时任务

站长推荐

上一篇
《LeetCode》—— 哈希

下一篇
C#--使用Quartz实现定时任务