此处将为大家介绍关于ReverseLinkedListII的详细内容，此外，我们还将为您介绍关于(Easy)ReverselinkedlistLeetCode、02-线性结构3ReversingLin
此处将为大家介绍关于Reverse Linked List II的详细内容，此外，我们还将为您介绍关于(Easy) Reverse linked list LeetCode、02 - 线性结构 3 Reversing Linked List （25 分)、02-线性结构3 Reversing Linked List、1074 Reversing Linked List的有用信息。
本文目录一览：- Reverse Linked List II
- (Easy) Reverse linked list LeetCode
- 02 - 线性结构 3 Reversing Linked List （25 分)
- 02-线性结构3 Reversing Linked List
- 1074 Reversing Linked List
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.
Discuss
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseList(ListNode *root)
{
if(!root||!root->next)
return root;
ListNode *p,*q,*tem;
p = root;
q = NULL;
while(p)
{
if(!q)
{
p = p->next;
q = root;
q->next = NULL;
continue;
}
tem = p;
p = p->next;
tem->next = q;
q = tem;
}
return q;
}
ListNode *reverseBetween(ListNode *head, int m, int n)
{
if(NULL==head||NULL==head->next||m==n)
return head;
ListNode *mp = head; // the point to the head of list
ListNode *np = head; // the tail of list
ListNode *mp1; // the head of list
ListNode *np1;
ListNode *newhead;
while(n!=1&&n--)
np = np->next;
if(m==1&&NULL==np->next)
return reverseList(head);
if(m==1&&NULL!=np->next)
{
np1 = np->next;
np->next = NULL;
newhead = reverseList(head);
head->next = np1;
return newhead;
}
while(m!=2&&m--)
mp = mp->next;
mp1 = mp->next;
np1 = np->next;
np->next = NULL;
reverseList(mp1);
mp->next = np;
mp1->next = np1;
return head;
}
};
(Easy) Reverse linked list LeetCode
Description:
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution:
Explanation:
Iterative Method
- Initialize three pointers prev as NULL,curr as head and next as NULL.
- Iterate trough the linked list. In loop,do following.
// Before changing next of current,
// store next node
next = curr->next// Now change next of current
// This is where actual reversing happens
curr->next = prev// Move prev and curr one step forward
prev = curr
curr = next
/** * DeFinition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev =null,curr = head,next = null; while(curr!=null){ next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }
02 - 线性结构 3 Reversing Linked List （25 分)
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤) which is the total number of nodes, and a positive K (≤) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100010;
struct Node{
int address,data,next;
int flag;
}node[maxn];
bool cmp(Node a,Node b){
return a.flag < b.flag;
}
//void print(int i,int k,int n){
// int j;
// for(j = i + k - 1; j >= i; j--){
// printf("%05d %d ",node[j].address,node[j].data);
// if(j > i){
// printf("%05d\n",node[j-1].address);
// }else{
// if(i+2*k<=n){
// printf("%05d\n",node[i+2*k].address);
// }
// }
// }
//}
int main(){
for(int i = 0 ; i < maxn; i++){
node[i].flag = maxn;
}
int n,k,begin;
scanf("%d%d%d",&begin,&n,&k);
int address;
for(int i = 0; i < n; i++){
scanf("%d",&address);
scanf("%d%d",&node[address].data,&node[address].next);
node[address].address = address;
//node[address].flag = maxn;
}
int count = 0,p = begin;
while(p!=-1){
node[p].flag = count++;
p = node[p].next;
}
sort(node,node+maxn,cmp);
n = count;
for(int i = 0; i < n/k; i++){
for(int j = (i+1)*k-1; j > i*k; j--){
printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);
}
printf("%05d %d ",node[i*k].address,node[i*k].data);
if(i < n/k-1) printf("%05d\n",node[(i+2)*k-1].address);
else{
if(n%k==0) printf("-1\n");
else{
printf("%05d\n",node[(i+1)*k].address);
for(i = n/k*k; i < n; i++){
printf("%05d %d ",node[i].address,node[i].data);
if(i < n-1) printf("%05d\n",node[i+1].address);
else printf("-1\n");
}
}
}
}
// if(n == 1){
// printf("%05d %d -1\n",node[0].address,node[0].data);
// return 0;
// }
// bool flag = true;
// if(count%k!=0){
// while(count%k!=0) count--;
// flag = false;
// }
// for(int i = 0; i < count; i += k){
// print(i,k,count);
// }
//
// if(flag == true){
// printf("-1\n");
// }else{
// printf("%05d\n",node[count].address);
// for(int i = count; i < n; i++){
// printf("%05d %d ",node[i].address,node[i].data);
// if(i < n - 1) printf("%05d\n",node[i+1].address);
// else printf("-1\n");
// }
// }
//
// for(int i = 0; i < n; i++){
// printf("%05d %d\n",node[i].address,node[i].data);
// }
return 0;
}
02-线性结构3 Reversing Linked List
题目
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3K = 3K=3, then you must output 3→2→1→6→5→4; if K=4K = 4K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N(≤$10^{5}$) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Nextwhere Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
99999 5 68237
12309 2 33218Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1注意
supposed to reverse the links of every K elements on L（反转每k个数）
The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1
解法1：利用空间换时间
定义一个长10000数组，下标表示每行的Address值。
根据结点的顺序，依次加入到一个vector中。
对vector中的每个K元素进行反转。
输出最终结果
#include <iostream>
#include <vector>
using namespace std;
#define MAX_ADDRESS_SIZE 100000
struct Node
{
int Address = -1;
int Data = 0;
int Next = -1;
};
void reverse_linked_nodes(vector<Node>& list, int start, int end)
{
while (start < end)
{
Node temp = list[start];
list[start] = list[end];
list[end] = temp;
start++;
end--;
}
}
int main()
{
// read first command line
int head_addr, node_count, reverse_node_count;
cin >> head_addr >> node_count >> reverse_node_count;
// read list nodes
vector<Node> nodes(MAX_ADDRESS_SIZE);
for (int i = 0; i < node_count; i++)
{
int addr, data, next;
cin >> addr >> data >> next;
nodes[addr].Address = addr;
nodes[addr].Data = data;
nodes[addr].Next = next;
}
// insert to vector with sorted
vector<Node> node_list;
node_list.push_back(nodes[head_addr]); // push the first node
while (node_list.back().Next != -1)
{
node_list.push_back(nodes[node_list.back().Next]); //push the next node
}
// reverse every reverse_count elements of real link list
int reverse_times = node_list.size() / reverse_node_count;
for (int i = 0; i < reverse_times; i++)
{
int start = i * reverse_node_count;
int end = start + reverse_node_count -1;
reverse_linked_nodes(node_list, start, end);
}
// output result
for (int i = 0; i < node_list.size()-1; i++)
{
printf("%05d %d %05d\n", node_list[i].Address, node_list[i].Data, node_list[i+1].Address);
}
printf("%05d %d %d\n", node_list.back().Address, node_list.back().Data, -1);
return 0;
}
1074 Reversing Linked List
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.
Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1和乙级的1025一样：1025 反转链表 (25 分)_Brosto_Cloud的博客-CSDN博客
Data 和 Next 数组的下标 i 都是地址，表示对应地址的数据和链接的下一个地址，list数组下标 i 是顺序，代表节点地址，每个地址对应的数据都是不变的，改变的只是链接的下一个地址，所以对list 数组每k个进行反转后直接输出 list[i]和list[i+1]就是对应的地址顺序，data[i]是对应的数据。
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
int Data[100010], list[100010], Next[100010];
int n, k, addr, t, sum;
int main() {
cin >> addr >> n >> k;
for (int i = 0; i < n; i++) {
cin >> t;
cin >> Data[t] >> Next[t];
}
while (addr != -1) {
list[sum++] = addr;
addr = Next[addr];
}
for (int i = 0; i < (sum - sum % k); i += k) {
reverse(list + i, list + i + k);
}
for (int i = 0; i < sum - 1; i++) {
cout << setfill('0') << setw(5) << list[i] << ' ' << Data[list[i]] << ' ' << setfill('0') << setw(
5) << list[i + 1] << endl;
}
cout << setfill('0') << setw(5) << list[sum - 1] << ' ' << Data[list[sum - 1]] << ' ' << -1;
return 0;
}今天关于Reverse Linked List II的介绍到此结束，谢谢您的阅读，有关(Easy) Reverse linked list LeetCode、02 - 线性结构 3 Reversing Linked List （25 分)、02-线性结构3 Reversing Linked List、1074 Reversing Linked List等更多相关知识的信息可以在本站进行查询。
本文标签：
