Reversing Linked List (25)

//方法1：用数组模拟
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
int main() {
    int first, k, n, adress,count=0;
    cin >> first >> n >> k;
    int data[maxn], next[maxn], order[maxn];
    for (int i = 0; i < n; i++) {
        cin >> adress;
        cin >> data[adress] >> next[adress];
    }
    while (first != -1) {
        order[count++] = first;
        first = next[first];
    }
    n=count;
    for (int i = 0; i < (n - n % k); i += k)
        reverse(order + i, order + i + k);
    for (int i = 0; i < n - 1; i++)
        printf("%05d %d %05d\n", order[i], data[order[i]], order[i + 1]);
    printf("%05d %d -1", order[n - 1], data[order[n - 1]]);
    return 0;
}


//方法2：用双链表过的了PAT过不了牛客所有数据
#include <iostream>
#include <string>
using namespace std;
const int maxn=100010;
struct Node{
 int data,next,pre;
}node[maxn];
int order[maxn];
int main(){
 int n,k,head,group,num,count=0;
 cin>>head>>n>>k;
 for(int i=0;i<n;i++){
  cin>>num;
  cin>>node[num].data;
  cin>>node[num].next;
 }
 node[head].pre=-1;
 num=head;
 for(int i=1;i<=n;i++){
  count++;
  order[i]=num;
  if(node[num].next==-1) break;
  node[node[num].next].pre=num;
  num=node[num].next;
 }
 n=count;
 group=n/k;
 for(int i=1;i<=group;i++){
  num=order[i*k];
  for(int j=1;j<=k;j++){
   printf("%05d %d ",num,node[num].data);
   if(j!=k){
    printf("%05d\n",node[num].pre);
    num=node[num].pre;
   }
   else if(i<group)
    printf("%05d\n",order[(i+1)*k]);
   else if(n%k==0) printf("-1\n");
   else{
    printf("%05d\n",node[order[i*k]].next);
    num=node[order[i*k]].next;
   }
  }
 }
 if(n%k!=0){
  k=n%k;
  for(int j=1;j<=k;j++){
   printf("%05d %d ",num,node[num].data);
   if(j!=k){
    printf("%05d\n",node[num].next);
    num=node[num].next;
   }
   else printf("-1\n");
  }
 }
 return 0;
} 

	#include <iostream>



	#include <vector>



	#include <algorithm>



	#include <iomanip>



	using namespace std;



	 



	struct node{



	    intaddress;



	    intvalue;



	    node(inta, intv){



	        address = a;



	        value = v;



	    }



	};



	intmain(){



	    intfirst, n, k;



	    cin >> first >> n >> k;



	     



	    intnumber[100005][2];



	    for(inti = 0; i < n; i++){



	        intaddress, data, next;



	        cin >> address >> data >> next;



	        number[address][0] = data;



	        number[address][1] = next;



	    }



	     



	    vector<node> num;



	    while(first != -1){



	        num.push_back(node(first, number[first][0]));



	        first = number[first][1];



	         



	        if(num.size() % k == 0){



	            reverse(num.end()-k, num.end());



	        }



	    }



	     



	    for(inti = 0; i < num.size(); i++){



	        cout <<setfill('0') << setw(5) << num[i].address << " "<< num[i].value << " ";



	        if(i != num.size() - 1){



	            cout <<setfill('0') << setw(5) << num[i+ 1].address << endl;



	        }else{



	            cout << "-1"<< endl;



	        }



	    }



	     



	     



	     



	    return0;



	}

#include<cstdio>
using namespace std;
class Node{
public:
  int addr;
  int val;
  Node* next;
  Node():next(NULL){}
};
Node nodes[100000];
void printList(Node* head){
    while(head != NULL){
        printf("%05d %d ",head->addr,head->val);
        if(head->next != NULL) printf("%05d\n",head->next->addr);
        else printf("-1\n");
        head = head->next;
    }
}
Node* reverseList(Node* head){
    Node* prev = NULL;
    while(head){
        Node* tmp = head->next;
        head->next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}
Node* reverseListByK(Node* head,int k){
    if(!head || !head->next) return head;
    int i = 0;
    Node* tmp = head;
    for(; i < k-1 && head; i++){
        head = head->next;
    }
    if(head == NULL){
        return tmp;
    }else{
        Node* nextH = head->next;
        head->next = NULL;
        Node* pre = reverseList(tmp);
        Node* res = reverseListByK(nextH,k);
        tmp->next = res;
        return pre;
    }
}
int main(){
    int hAddr,N,K;
    Node* head = NULL;
    scanf("%d %d %d",&hAddr,&N,&K); 
    for(int i=0 ; i < N; i++){
        int addr,val,naddr;
        scanf("%d %d %d",&addr,&val,&naddr);
        nodes[addr].addr = addr;
        nodes[addr].val = val;
        if(naddr != -1) nodes[addr].next = &nodes[naddr];
        if(addr == hAddr) head = &nodes[addr];
    }
    Node* nhead = reverseListByK(head,K);
    printList(nhead);
    return 0;
}

#include<cstdio>
(802)#include<iostream>
using namespace std;

struct node {
	int addr;
	int data;
	node* next;
};
typedef node* List;
node lists[100007];

void reverse(List head, int k, int n)
{
	List new_head, old_head, temp;
	List succ, prev;
	List p = head;
	prev = p;

	int i;
	for (i = 1; i <= n && p; i++)
	{
		p = p->next;

		if (i % k == 0)
		{
			old_head = prev->next;
			new_head = NULL;
			succ = p->next;
			
			while (old_head != succ)
			{
				temp = old_head;
				old_head = old_head->next;
				temp->next = new_head;
				new_head = temp;
			}

			p = prev;
			while (p->next)
				p = p->next;

			p->next = succ;
			prev->next = new_head;

			prev = p;
		}
	}
}

void print(List head)
{
	List p = head->next;
	while (p)
	{
		if(p->next)
			printf("%05d %d %05d\n", p->addr, p->data, p->next->addr);
		else
			printf("%05d %d -1", p->addr, p->data);
		p = p->next;
	}
}

void freeList(List list)
{
	List p = list, temp;
	while (p)
	{
		temp = p;
		p = p->next;
		free(temp);
	}
}

int main()
{
	int n, k, faddr;
	List head = new node;
	ios::sync_with_stdio(false);
	cin >> faddr >> n >> k;
	for(int i = 0; i < n; i++)
	{
		int addr, data, naddr;
		cin >> addr >> data >> naddr;
		lists[addr].addr = addr;
		lists[addr].data = data;
		if(naddr != -1) 
			lists[addr].next = &lists[naddr];
		if(addr = faddr)
			head->next = &lists[addr];
	}
	reverse(head, k, n);
	print(head);
    delete head;
	//freeList(head);
}

tem = list(map(str,input().split()))
start,n,k  = tem[0],int(tem[1]),int(tem[2])
lst,lst1 = [None,None]*100001,[]
for i in range(0,n):
    a,b,c = map(str,input().split())
    lst[int(a)] = [b,c]
tem = []
while start!='-1': 
   tem.append([start,lst[int(start)][0]])
   start = lst[int(start)][1]
   if len(tem)==k:
       lst1.extend(tem[::-1])
       tem = []
lst1.extend(tem)
for i in range(0,len(lst1)-1):
    print(lst1[i][0]+" "+lst1[i][1]+" "+lst1[i+1][0])
print(lst1[len(lst1)-1][0]+" "+lst1[len(lst1)-1][1]+" "+"-1") 

start,N,K=map(int,input().split())
L=[None,None]*100005
for i in range(N):
    a,b,c=map(int,input().split())
    L[a]=[b,c]
res,tmp=[],[]
while start!=-1:
    tmp.append([start,L[start][0]])
    start=L[start][1]
    if len(tmp)==K:
        res.extend(tmp[::-1])
        tmp=[]
else:
    res.extend(tmp)
for i in range(len(res)-1):
    print('{:05d} {} {:05d}'.format(res[i][0],res[i][1],res[i+1][0]))
print('{:05d} {} {}'.format(res[-1][0],res[-1][1],-1))

测试用例全部通过，内存用得多了。

#include<cstdio>
#include<stack>
#include<iostream>
using namespace std;
struct Node {
    int now;
    int data;
    int next;
}node[1000010],tp[1000010],prt[1000010],t;
int main() {
    int fstad, K, N;
    scanf("%d%d%d", &fstad, &N, &K);
    int temp;
    for (int i = 0; i < N; i++) {
        scanf("%d", &temp);
        node[temp].now = temp;
        scanf("%d%d",&node[temp].data, &node[temp].next);
    }
    t = node[fstad];
    int cnt = 1;
    tp[0] = t;
    while (t.next!= -1) {
        tp[cnt++] = node[t.next];
        t = node[t.next];
    }
    int length = cnt;
    stack<Node> st;
    cnt = 0;
    for (int i = 0; i+K <=length; i+=K) {
        for (int j = i; j < i + K; j++) {
            st.push(tp[j]);
        }
        while (!st.empty()) {
            prt[cnt++] = st.top();
            st.pop();
        }
    }
    for (int i = cnt; i < length; i++) {
        prt[i] = tp[i];
    }
    for (int i = 0; i < length-1; i++) {
        prt[i].next = prt[i + 1].now;
    }
    prt[length- 1].next = -1;
    for (int i = 0; i <length; i++) {
        if(i<length-1)
            printf("%05d %d %05d\n", prt[i].now, prt[i].data, prt[i].next);
        else
            printf("%05d %d %d", prt[i].now, prt[i].data, prt[i].next);
    }
}

import java.util.HashMap;
import java.util.Scanner;

public class Main8 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String headAddress = in.next();
		int N = in.nextInt();
		int K = in.nextInt();
		HashMap<String, Node> map = new HashMap<>();
		for (int i = 0; i < N; i++) {
			String address = in.next();
			int val = in.nextInt();
			String nextAddress = in.next();
			Node node = map.get(address);
			if (node == null) {
				node = new Node();
				node.address = address;
				node.val = val;
				Node next = map.get(nextAddress);
				if (next == null) {
					next = new Node();
					next.address = nextAddress;
				}
				node.next = next;
				map.put(address, node);
				map.put(nextAddress, next);
			} else {
				node.val = val;
				Node next = map.get(nextAddress);
				if (next == null) {
					next = new Node();
					next.address = nextAddress;
				}
				node.next = next;
				map.put(address, node);
				map.put(nextAddress, next);
			}
		}
		Node head = map.get(headAddress);
		map.clear();
		head = reverseKGroup(head, K);
		while (head != null && !head.address.equals("-1")) {
			System.out.println(head.address + " " + head.val + " " + head.next.address);
			head = head.next;
		}

	}

	public static Node reverseKGroup(Node head, int k) {
		Node cur = head;
		int count = 0;
		while (cur != null && !cur.address.equals("-1") && count != k) {
			cur = cur.next;
			count++;
		}
		if (count == k) {
			cur = reverseKGroup(cur, k);
			while (count-- > 0) {
				Node tmp = head.next;
				head.next = cur;
				cur = head;
				head = tmp;
			}
			head = cur;
		}
		return head;
	}
}

class Node {
	int val;
	String address;
	Node next;
}

public class Main {
 	    public static final int MAX=100000;
    public Node[] list;
    public int headAddress,rhead;
    public int N,K;
    public class Node{
        int data=0;
        int next=0;
        int address=0;
        public Node(int address,int data,int next){
            this.address=address;
            this.data=data;
            this.next=next;
        }
    }


    public void createPoly(){
        int nodeAddress,i=0;
        int data,next;
        Scanner s=new Scanner(System.in);
        headAddress=s.nextInt();
        N=s.nextInt();
        K=s.nextInt();

        if(headAddress<0||headAddress>99999||N>100000||N<0||K<0)
        {
            System.out.println("Input Error");
            return;
        }
        //variable can be declared but not initilize,
        //here we initialize the list!
        list=new Node[MAX];
        while(i<N){
            //Actually,it is not needed to use getLine.
           String str=s.nextLine();
            String[] arr=str.split(" ");
            int[] arrx=new int[arr.length];
            for(int k=0;k<arr.length;k++){
                 arrx[k]=Integer.parseInt(arr[k]);
            }
            nodeAddress=s.nextInt();
            data=s.nextInt();
            next=s.nextInt();
            list[nodeAddress]=new Node(nodeAddress,data,next);

            i++;
        }
    }

    public void printList(Node[] xlist,int xheadAddress){
        while(xlist[xheadAddress].next!=-1){
            System.out.printf("%05d %d %05d\n",xheadAddress,xlist[xheadAddress].data,xlist[xheadAddress].next);
            xheadAddress=xlist[xheadAddress].next;
        }
        System.out.printf("%05d %d %05d\n",xheadAddress,xlist[xheadAddress].data,xlist[xheadAddress].next);

    }

    public Node[] reverse(){
        //list
        Stack<Node> s1=new Stack<Node>();
        Node[] rlist=new Node[MAX];
        int rheadAddress=0,rear=0,Last=0;
        if(N<K)
            return null;
        int count=N/K;

        while(count>0){
            for(int i=0;i<K;i++){
                s1.push(list[headAddress]);
                rheadAddress=headAddress;
                headAddress=list[headAddress].next;
            }
            if(count==N/K)
            {
                rhead=s1.peek().address;
            }
            count--;
            for(int j=0;j<K;j++){
                //if N%K==0 , it will pop
                if(!s1.empty()){
                    //这里花费了一晚上，对于内存管理的不了解！
                    Node xtmp=s1.pop();
                    Node tmp=new Node(xtmp.address,xtmp.data,xtmp.next);
                    rlist[rheadAddress]=tmp;
                    if(count==0&&j==0){
                        Last=tmp.address;
                    }
                    //using top()!!!!!!!
                    if(s1.empty()){
                        if(count==0)
                            rear=tmp.address;
                        break;
                    }
                    rlist[rheadAddress].next=s1.peek().address;
                    rheadAddress=rlist[rheadAddress].next;
                }
            }
        }
        System.out.printf("%d %d\n",Last,rear);
        if(N%K!=0){
            int num=N%K+1;//Start from the node "1", the node rear.
            //So including rear there shall add 1.
            while(num>0){
                Node tmp=new Node(rear,list[rear].data,list[Last].next);
                rlist[rear]=tmp;
                //rlist[rear].next=list[Last].next;
                Last=list[Last].next;
                rear=Last;
                num--;
            }

        }
        return rlist;

    }

    public static void main(String[] args) {
     	Main r=new Main();
        Scanner s=new Scanner(System.in);
      /*  int[] arrx=new int[4];
        String str=s.nextLine();
        String[] arr=str.split(" ");
        for(int i=0;i<arr.length;i++){
            arrx[i]=Integer.parseInt(arr[i]);
        }
        System.out.println(arrx[0]);
        System.out.println(arrx[1]);
*/
        Node[] rlist;
        r.createPoly();
        r.printList(r.list,r.headAddress);
        rlist=r.reverse();

        System.out.println(rlist[r.rhead].data);
        int rhead=r.rhead;
       r.printList(rlist,rhead);
    }
   
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

struct Node
{
    int address, val;
    Node(int _address, int _val) {
        address = _address;
        val = _val;
    }
    Node() {}
};

int data[100000][2];

int main()
{
    // 读入数据
    int startAdress, N, K; scanf("%d %d %d", &startAdress, &N, &K);
    int address, val, next;
    while(N--) {
        scanf("%d %d %d", &address, &val, &next);
        data[address][0] = val;
        data[address][1] = next;
    }
    vector<Node> rlt; address = startAdress; int idx1=0, idx2=0;
    while(address != -1) {
        rlt.push_back(Node(address, data[address][0]));
        address = data[address][1];
        idx2++;
        if(idx2%K == 0) {
            reverse(rlt.begin()+idx1, rlt.begin()+idx2);
            idx1 = idx2;
        }
    }
    for(int i=0; i<idx2-1; i++) {
        printf("%05d %d %05d\n", rlt[i].address, rlt[i].val, rlt[i+1].address);
    }
    printf("%05d %d -1\n", rlt[idx2-1].address, rlt[idx2-1].val);
    return 0;

}