`
jgsj
  • 浏览: 951799 次
文章分类
社区版块
存档分类
最新评论

Leetcode Reverse Linked List II 反转特定区间的链表

 
阅读更多

Reverse Linked List II


Reverse a linked list from positionmton. Do it in-place and in one-pass.

For example:
Given1->2->3->4->5->NULL,m= 2 andn= 4,

return1->4->3->2->5->NULL.

Note:
Givenm,nsatisfy the following condition:
1 ≤mn≤ length of list.

这样的题目关键是不要怕麻烦,一定要画多几个链表图,一步一步演算,这样思路就很清晰了。

通过头痛折磨的训练之后,这些题目不用调试,一次性AC。

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 dummy(0);
		dummy.next = head;
		ListNode *pre = &dummy;

		for (int i = 1; i < m; i++)
		{
			pre = cur;
			cur = cur->next;
		}

		ListNode *post;
		ListNode *ppost;
		if (cur) ppost = cur;
		if (ppost) post = ppost->next;
		for (int j = m; j <= n; j++)
		{
			ppost->next = cur;
			cur = ppost;
			ppost = post;
			if (post) post = post->next;
		}
		pre->next->next = ppost;
		pre->next = cur;

		return dummy.next;
	}
};

上面是逆转法,下面是插入法 2014-1-10更新:

ListNode *reverseBetween(ListNode *head, int m, int n) 
	{
		if (!head || m==n) return head;
		ListNode dummy(-1);
		dummy.next = head;
		ListNode *pre = &dummy;

		for (int i = 1; i < m; i++)
		{
			pre = pre->next;
		}

		ListNode *insertPre = pre->next;
		for (int i = m; i < n; i++)
		{
			ListNode *cur = insertPre->next;
			insertPre->next = cur->next;
			cur->next = pre->next;
			pre->next = cur;
		}
		return dummy.next;
	}


//2014-2-14 update
	ListNode *reverseBetween(ListNode *head, int m, int n) 
	{
		ListNode dummy(0);
		ListNode *p = &dummy;
		dummy.next = head;

		for (int i = 1; i < m; i++) p = p->next;
		head = p->next;

		for ( ; m < n; m++)
		{
			ListNode *tmp = head->next;
			head->next = tmp->next;
			tmp->next = p->next;
			p->next = tmp;
		}
		return dummy.next;
	}

















分享到:
评论

相关推荐

    fuxuemingzhu#Leetcode-Solution-All#92. Reverse Linked List II 反转

    进行一次遍历,把第m到n个元素进行翻转,即依次插入到第m个节点的头部。这个题还是有意思的。建议后面再多做几遍。Python代码如下:self.next = No

    Leetcode 反转链表.js

    LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...

    leetcode中文版-LeetCode:力码

    leetcode中文版 LeetCode/Cpp 本人刷题记录在此,包含题意理解与算法思路,包含在Cpp文件内部注释,后续会持续更新。 有不懂的可以联系ji648513181,同时也欢迎志同道合O的朋友一起合作更新。 已更新剑指Offer答案...

    leetcode中325题python-leetcode:leetcode

    reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表 linked-list-cycle 142 环形链表 II linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双...

    leetcode分发糖果-ForDaFactory:使用C++的个人leetcode解决方案

    92-反转链表II:reverse-linked-listt-ii 141-环形链表:linked-list-cycle 142-环形链表:linked-list-cycle-ii 160-相交链表:intersection-of-two-linked-lists 206-反转一个单链表:reverse-linked-list 20-有效的...

    leetcode跳跃-LeetCode:力扣刷题70道!

    Reverse Linked List 队列 Queue 力扣 933 最近的请求次数 | Number of Recent Calls 力扣 225 用队列实现栈 | Implement Stack Using Queue 力扣 622 设计循环队列 | Design Circular Queue 力扣 641 设计循环双端...

    leetcode2sumc-LeetCode:LeetCode的一些题目

    List(链表) ID Difficulty Title Java Python 21 Easy Merge Two Sorted Lists 83 Easy Remove Duplicates from Sorted List 141 Easy Linked List Cycle 160 Easy Intersection of Two Linked Lists 203 Easy ...

    LeetCode:LeetCode解决方案

    preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...

    Python实现数据结构与算法——反转链表

    链接:https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解题思路: 思路1:迭代 假设有链表1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;None, 反转后得None&lt;-...

    tech.github.io:我的博客

    终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。... Reverse Linked ListLeetcode 141. Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-...

    leetcode338-Leetcode:一些过滤leetcode问题的解决方案

    Leetcode 问题的 Python 解决方案 下面列出了这些问题的概述。 这些问题主要分为数据结构和算法两部分。 代码可以在此存储库的相应文件夹中找到。 数据结构: 细绳: 问题及解决方法: 242.有效字谜:| 409.最长回文...

    leetcode双人赛-java_leetcode:java打印letcode

    leetcode双人赛 工程共分为两个文件夹: A.Alogrithm 算法导论视频、书的相关程序,用于学习算法及数据结构的基础知识 B.Item 零基础学算法(戴艳) 的课后习题 C. leetcode的题目解答,按题目顺序进行排序 Given an...

    leetcodepushfront-leetcode:leetcode问题

    leetcode 推前当前问题 5 从 9 月 9 日到 12 月 9 日,按类型。 100 个主题和 Google。 力码 Leetcode 题目汇总 分类 1、求和问题 1.1 (1) Two Sum 1.2 (15) 3 Sum 1.3 (18) 4 Sum 1.4 (454) 4 Sum II 1.5 (167) Two...

    如何有效率的刷leetcode-LeetCodeLearn:力码学习

    如何有效率的刷leetcode LeetCodeLearn 学习算法基础知识以及对应高频题目的解决 IDE刷题插件:(推荐IntelliJ,可以查看MD文件) 目录: Array数组 Linked List链表 栈 队列 Tree数 遍历、排序 分治 动态规划 2.链表 ...

    leetcode备忘录系统-Algorithms-DataStructures:算法-数据结构

    反转链表 合并两个排序列表 回文链表 树(n-ary、trie、heap) 四叉树 中序、前序、后序遍历 二叉树的最大深度 验证二叉搜索树 将有序数组转换为二叉搜索树 面向对象编程术语 - Abstraction - Inheritance - ...

    leetcode卡-arts:每周输出:Algorithm+Review+Tip+Share

    leetcode卡 什么是ARTS? Algorithm:每周至少做一个 leetcode 的算法题 ...Algorithm:reverse-linked-list-ii(链表) Review:linux编程接口 Tip:ps进程 Share:源码阅读 - Redis数据结构底层实现

    leetcode中国-leetcode:刷算法了

    leetcode中国 Leetcode Set Matrix Zeroes 第一种 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引) 再遍历一次, 根据记录的索引进行置0 第二种 通过一次遍历所有为0的索引, 设置当前索引的...

    《剑指Offer》刷题笔记——面试题24. 反转链表

    # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None from collections import deque class Solution: def reverseList(self, head: ListNode) -...

Global site tag (gtag.js) - Google Analytics