问题描述:
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.
原问题链接:https://leetcode.com/problems/reverse-linked-list-ii/
问题分析
这个问题是反转单链表问题的一个稍微的变化,在之前的文章里也有讨论过。我们有了前面反转链表的基础再来看这个问题的话,基本的思路如下。
首先需要找到第n个元素所在的位置,然后再找到第m个元素所在的位置。因为我们这里反转元素的时候是从第m个开始的,需要一个指向m的前一个元素的引用。这样在后面的调整中才能保证前面的引用能够反转过来。为了得到这个之前一个的节点,我们需要定义一个临时节点dummy,它的next指向head。这样它往前移动m步就正好指向第m个元素的前一个。
后面在反转完链表之后还有一个细节就是我们这里要记录这里开始和结束节点它们所指向的下一个元素的位置。所以需要额外定义变量prev来保存。关于这些引用调整的细节比较繁琐,在详细实现之前最好画图先详细分析一下。这里就不再画图赘述了。
详细的代码实现如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(m == n) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode start = findNode(head, m); ListNode prev = findNode(dummy, m); ListNode end = findNode(head, n); if(start == null || end == null || prev == null) return head; ListNode pre = null, temp; while(start != end) { temp = start; start = start.next; temp.next = pre; pre = temp; } temp = start.next; start.next = pre; prev.next.next = temp; prev.next = start; return dummy.next; } private ListNode findNode(ListNode head, int n) { while(head != null && n - 1 > 0) { head = head.next; n--; } return head; } }
相关推荐
92.Reverse Linked List II LeetCode 138.Copy List with Random Pointer LeetCode 142.Linked List Cycle II(solve1) LeetCode 142.Linked List Cycle II(solve2) LeetCode 160.Intersection of Two Linke
进行一次遍历,把第m到n个元素进行翻转,即依次插入到第m个节点的头部。这个题还是有意思的。建议后面再多做几遍。Python代码如下:self.next = No
Linked_list_cycle.py: long_pressed_name.py: max_69_number.py: max_array_sum_after_negations.py: max_depth_n_ary_tree.py: max_string_split_score.py: max_sub_array.py: merge_2_trees.py: plus_one...
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 ...complexitypython.txt Python的一些常规操作的复杂度统计 ...Reverse Linked List 234 Easy Palindrome Linked List
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 问题的 Python 解决方案 下面列出了这些问题的概述。 这些问题主要分为数据结构和算法两部分。 代码可以在此存储库的相应文件夹中找到。 数据结构: 细绳: 问题及解决方法: 242.有效字谜:| 409.最长回文...
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动态规划
leetcode 推前当前问题 5 从 9 月 9 日到 12 月 9 日,按类型。 100 个主题和 Google。 力码 Leetcode 题目汇总 分类 1、求和问题 1.1 (1) Two Sum 1.2 (15) ...II ...II ...Reverse Linked List 概括 对于
Reverse Linked List 队列 Queue 力扣 933 最近的请求次数 | Number of Recent Calls 力扣 225 用队列实现栈 | Implement Stack Using Queue 力扣 622 设计循环队列 | Design Circular Queue 力扣 641 设计循环双端...
leetcode盒子嵌套 leetcode-text 92.Reverse Linked List II Runtime: 4 ms, faster than 67.04% of C online submissions for Reverse Linked List II. Memory Usage: 6.9 MB, less than 100.00% of C online ...
Reverse Polish Notation 逆波兰的后半截实现 Linked List Cycle 快慢指针 Linked List Cycle II 快慢指针再加个初始指针 慢指针到链表开始位置时, 快指针总是比他快k步(每次移动快1步, 移动k次), 第一次相遇的时候...
reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode node = reverseList(head.next); head.next.next = head; head.next = null; return node; } } 迭代 /** * Definition ...
leetcode 不会 Leetcode Solutions in Java Linked List Linked List ...linked list, ...快慢指针法,块指针从head.next开始,慢指针从head开始,快指针每次移动两格,慢...reverseList(ListNode head) 三个指针,依次往后
Linked List 3 Longest Substring Without Repeating Characters (无重复字符的最长子串) Medium Dual Pointer (Sliding Window), Hash Table 4 Median of Two Sorted Arrays (寻找两个有序数组的中位数) Hard ...
reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. 新建一个链表,同时向后遍历两个链表,将他们的value相加 Given a string, find the
leetcode添加元素使和等于 总结 按照类别分类来刷 刷当前题的时候,看下『题目描述』最底下有个『相似题目』,这些题的思路...linked-list-cycle-ii reverse-nodes-in-k-group 二叉树 实现一个二叉树 二叉树二叉树的
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-有效的...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。... Reverse Linked ListLeetcode 141. Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal
Linked List O(n) O(1) Sliding Window O(n) O(n) Binary-Search O(log (m+n)) O(1) GO JAVA DP String O(n) O(n) [GO](. Reverse Integer/ri7.go) [JAVA](. Reverse Integer/Solution.java) Math O(log(x)) O(1) ...