【题目】
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 ≤m≤n≤ length of list.
【题意】
将给定链表第m个节点到第n个节点的位置逆序,返回逆序后的链表。
给定M,N满足以下条件:
1≤M≤N≤列表的长度。
【分析】
思路1:
前m-1个不变,从第m+1个到第n个,依次删除,用尾插法插入到第m-1个节点后面。
第一步把4节点删除放入2节点之后
第二步把5节点删除放入2节点之后
【代码1】
/*********************************
* 日期:2014-01-28
* 作者:SJF0115
* 题号: Reverse Linked List II
* 来源:http://oj.leetcode.com/problems/reverse-linked-list-ii/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
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) {
if(m > n || n < 0){
return head;
}
ListNode *tail,*p,*rTail,*pre = NULL;
//添加虚拟头结点(便于反转全部)
ListNode *beginNode = (ListNode*)malloc(sizeof(ListNode));
beginNode->next = head;
pre = beginNode;
int index = 1;
//遍历前m-1个节点
while(pre != NULL && index < m){
pre = pre->next;
index++;
}
tail = pre;
rTail = pre->next;
index = 1;
//删除第m+1节点开始
while(index < (n-m+1) ){
//删除p节点
p = rTail->next;
rTail->next = p->next;
//尾插法
p->next = tail->next;
tail->next = p;
index++;
}
return beginNode->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5,6,7,8,9};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 1;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.reverseBetween(head->next,1,8);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
return 0;
}
【代码2】
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode *preM, *pre = &dummy;
for (int i = 1; i <= n; ++i) {
//preM 第m-1个节点
if (i == m) preM = pre;
if (i > m && i <= n) {
//删除head节点
pre->next = head->next;
head->next = preM->next;
//尾插法
preM->next = head;
head = pre; // head has been moved, so pre becomes current
}
pre = head;
head = head->next;
}
return dummy.next;
}
};
分享到:
相关推荐
进行一次遍历,把第m到n个元素进行翻转,即依次插入到第m个节点的头部。这个题还是有意思的。建议后面再多做几遍。Python代码如下:self.next = No
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
终生成长 :hot_beverage: 为什么要建这个仓库 梳理自己掌握的知识点,整理自己的知识体系。... Reverse Linked ListLeetcode 141. Linked List CycleLeetcode 21. Merge Two Sorted ListsLeetCode 224. Basic Cal
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 submissions for Reverse Linked List ...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
LeetCode 206的题目是“反转链表”(Reverse Linked List),它要求将一个单链表的所有节点反转,并返回反转后链表的头节点。这是一个基础但非常重要的链表操作问题,它不仅考察了对链表数据结构的理解,还涉及到了...
list. Challenge: Reverse it in-place and in one-pass A linked list can be reversed either iteratively or recursively. Could you implement both? public static ListNode reverseList(ListNode head) 三个...
这是我准备面试时建议的个人问题清单。...https://leetcode.com/problems/reverse-linked-list/ https://leetcode.com/problems/linked-list-cycle/ https://leetcode.com/problems/merge-two-sorted-lists/ 2D阵列 ...
Leetcode 问题的 Python 解决方案 下面列出了这些问题的概述。 这些问题主要分为数据结构和算法两部分。 代码可以在此存储库的相应文件夹中找到。 数据结构: 细绳: 问题及解决方法: 242.有效字谜:| 409.最长回文...
leetcode 分类 数据结构和算法学习记录,结合LeetCode刷题 分类 DP 目录 题目 解法 分类 Time Space Array O(n) O(n) Linked List O(n) O(1) Sliding Window O(n) O(n) Binary-Search O(log (m+n)) O(1) GO JAVA DP ...
You are given two non-empty linked lists ... Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. java AC版本
Reverse Linked List中等的33. Search in Rotated Sorted Array74. Search a 2D Matrix I240. Search a 2D Matrix II2. Add Two Numbers50. Pow(x, n)34. First & LastPositionElementInSortedArr94. Binary Tree ...
92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-...
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 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 链接 complexitypython.txt Python的一些常规操作的复杂度统计 题目清单 Array(数组) ID Difficulty Title Java Python 1 Easy ...
https : //leetcode.com/problems/Reverse-Integer/description/ 反向链接列表: https : //leetcode.com/problems/Reverse-Linked-List/description/ 两次求和: https : //leetcode.com/problems/two-sum/
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-有效的...
Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 ...
Reverse-Linked-List-II 要点: - 确定边界条件,定位到起点 - 再利用头插法对指定段的链表逆序 链表逆序之头插法,关键代码(牢记): pre.next = cur.next; cur.next = head.next; head.next = cur; ...
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动态规划