[LeetCode] Reverse Linked List II

2024-06-05 08:48
文章标签 leetcode ii list linked reverse

本文主要是介绍[LeetCode] Reverse Linked List II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

解题思路

解题思路与上一篇Reverse Linked List类似,只不过这里是反转部分链表。
因此,只需将m到n部分翻转,然后将m的前缀beforeM指向该部分反转后的头结点即可。如果beforeM为NULL,则m=1,m到n部分的头结点即为链表的头结点。

实现代码

//Runtime: 4 ms
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;struct ListNode{int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode *cur = head;ListNode *beforeM = NULL;for (int i = 1; i < m; i++){beforeM = cur;cur = cur->next;}ListNode *localhead = cur;ListNode *pre = cur;cur = cur->next;int count = n - m;while (count--){pre->next = cur->next;cur->next = localhead;localhead = cur;cur = pre->next;}if (beforeM == NULL){head = localhead;}else{beforeM->next = localhead;}return head;}
};void printList(ListNode *head)
{while(head != NULL){cout<<head->val<<" ";head = head->next;}cout<<endl;
}void dropList(ListNode *head)
{if (head == NULL) return;ListNode *temp;while (head != NULL){temp = head->next;delete head;head = temp;}
}int main()
{ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 0; i < 10; i++){ListNode *newnode = new ListNode(floor(rand()%77));cur->next = newnode;cur = newnode;}printList(head);Solution s;head = s.reverseBetween(head, 2, 5);printList(head);dropList(head);
}

这篇关于[LeetCode] Reverse Linked List II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032614

相关文章

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》:本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

java streamfilter list 过滤的实现

《javastreamfilterlist过滤的实现》JavaStreamAPI中的filter方法是过滤List集合中元素的一个强大工具,可以轻松地根据自定义条件筛选出符合要求的元素,本文就来... 目录1. 创建一个示例List2. 使用Stream的filter方法进行过滤3. 自定义过滤条件1. 定

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

python中列表list切分的实现

《python中列表list切分的实现》列表是Python中最常用的数据结构之一,经常需要对列表进行切分操作,本文主要介绍了python中列表list切分的实现,文中通过示例代码介绍的非常详细,对大家... 目录一、列表切片的基本用法1.1 基本切片操作1.2 切片的负索引1.3 切片的省略二、列表切分的高