反转链表 (25)

本题有一个陷阱，输入的n会大于100000，有一些无效结点需要排除，所以不能以n作为链表长度而是要在排链表时重新计算一遍。

 import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int first = sc.nextInt();
		int nc = sc.nextInt();
		ArrayList<Node> ll = new ArrayList<Node>();
		int k = sc.nextInt();
		//节点地址-节点映射
		HashMap<Integer, Node> map = new HashMap<Integer, Node>();
		while(nc != 0){
			int ad = sc.nextInt();
			int val = sc.nextInt();
			int next = sc.nextInt();
			map.put(ad, new Node(ad, val, next));
			nc--;
		}
		sc.close();
		
		//把链表按给出顺序排列,放入集合中
		while(first != -1){
			Node n = map.get(first);
			ll.add(n);
			first = n.next;
		}
		
		//每k位逆转顺序
		for(int i = k; i < ll.size(); i += k){
			int l = i-k;
			int r = i-1;
			while(l < r){
				Node t = ll.get(l);
				ll.set(l, ll.get(r));
				ll.set(r, t);
				l++;
				r--;
			}
		}
		
		//输出结果,地址小于5位前面补0
		for(int i = 0; i<ll.size()-1; i++){
			String str = ""+ll.get(i).address;
			String str2 = ""+ll.get(i+1).address;
			while(str.length() < 5)
				str = "0"+str;
			while(str2.length() < 5)
				str2 = "0"+str2;
			System.out.println(str + " " + ll.get(i).val + " " + str2);
		}
		String str = ""+ll.get(ll.size()-1).address;
		while(str.length() < 5)
			str = "0"+str;
		System.out.println(str + " " + ll.get(ll.size()-1).val + " -1"); 
		
	}
	
	static class Node{
		public Node(int adr, int v, int next){
			address = adr;
			val = v;
			this.next = next;
		}
		int address;
		int val;
		int next;
	}

} 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
struct listnode {
 int data, next;
};
int main() {
 int first, n, k;
 listnode thelist[100002];
 cin >> first >> n >> k;
 int addri;
 for (int i = 0; i<n; i++) {
  cin >> addri;
  cin >> thelist[addri].data >> thelist[addri].next;
 }
 int count = 0;
 vector<int> addr(n + 1, -1);
 addr[0] = first;
 while (addr[count] != -1) {
  count++;
  addr[count] = thelist[addr[count - 1]].next;
 }
 for (int i = 0; i + k<=count; i += k) {
  reverse(addr.begin() + i, addr.begin() + i + k);
 }
 for (int i = 0; i<count - 1; i++) {
  thelist[addr[i]].next = addr[i + 1];
  printf("%05d %d %05d\n", addr[i], thelist[addr[i]].data, thelist[addr[i]].next);
 }
 thelist[addr[count - 1]].next = -1;
 printf("%05d %d -1", addr[count - 1], thelist[addr[count - 1]].data);
}

package test;
import java.util.*;

public class Main{
	static class Node{
		String address;
		String value;
		String next;
		
		public Node(String address, String value, String next) {
			this.address = address;
			this.value = value;
			this.next = next;
		}
		
	}
    public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            String start = sc.next();
            String temp= "";
            int n = sc.nextInt();
            int k = sc.nextInt();
            HashMap<String, Node> map = new HashMap<String, Node>(n);
            for(int i = 0; i < n; i++){
            	temp = sc.next();
            	map.put(temp, new Node(temp, sc.next(), sc.next()));
            }
            int count = 0;//记录真实结点数目
            Node [] nodes = new Node[n];
            Node p = map.get(start);
            
            while(p != null){
            	nodes[count++] = p;  //真实结点就放入数组
            	p = map.get(p.next);
            }
            
            p = map.get(start);
            
            if(count <= 2 || count < k){    //结点数小于等于2 或者真实结点数小于k直接输出
            	for (int i = 0; i < count; i++) {
					System.out.println(nodes[i].address + " " + nodes[i].value + " " + nodes[i].next);
				}
            	return;
            }
            n = count;    //一开始没有意识到有无效结点，就一直以输入的n做结点数，结果疯狂越界
            int i = k - 1;
            for(; i < n - (n % k); i += k){
            	for(int j = i; j > i - k; j--){
            		if(j == i - k + 1){
            			if(i + k < n)
            				System.out.println(nodes[j].address + " " + nodes[j].value 
                    				+ " " + nodes[i + k].address);
            			else
            			System.out.println(nodes[j].address + " " + nodes[j].value 
                				+ " " + nodes[i + 1].address);

            		}else
            			System.out.println(nodes[j].address + " " + nodes[j].value 
            					+ " " + nodes[j - 1].address);
            	}
            }
            i -= k;	
            for(++i; i < n; i++){
            	System.out.println(nodes[i].address + " " + nodes[i].value 
            				+ " " + nodes[i].next);
            }            
    }
}

这个题目实在是“一言难尽”，希望大家不要浪费太多时间在题目没有写出的坑上。如果你本地测试良好，但是线上不通过，检查以下坑：

• 题目输入可能包含无效节点，你需要自行遍历一遍链表来确定节点的真实数量
• 有效节点数可能小于 K，此时直接输出整个链表不要反转
• 有效节点数可能小于等于 2，此时也是直接输出（对应第7个检查点）

贴个通过全部测试点的代码，为了处理上面的坑加了一些莫名其妙的判断，大家理解一下。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        HashMap<String, Node> nodes = new HashMap<String, Node>();

        String beginAddress = in.next();
        int nodeNum = in.nextInt();
        int K = in.nextInt();

        for(int i = 0; i< nodeNum; i++) {
            String address = in.next();
            int data = in.nextInt();
            String nextAddress = in.next();
            nodes.put(address, new Node(address, data, nextAddress));
        }

        int validenodeNum = 0;
        Node countNode = nodes.get(beginAddress);

        while(countNode != null) {
            countNode = countNode.next(nodes);
            validenodeNum++;
        }

        Node judgeNdde = nodes.get(beginAddress);
        if(validenodeNum <= 2 || validenodeNum < K) {

            while(judgeNdde!=null) {
                System.out.println(judgeNdde);
                judgeNdde = judgeNdde.next(nodes);
            }
            return;

        }

        Node prev = nodes.get(beginAddress);
        Node current = prev.next(nodes);
        Node next = current.next(nodes);
        Node beginNode = prev;
        Node prevBeginNode = null;

        Node printNode = null;

        while(validenodeNum >= K) {
            for(int i = 2; i < K; i++) {
                current.nextAddress = prev.address;
                prev = current;
                current = next;
                next = next.next(nodes);
            }

            current.nextAddress = prev.address;

            if(printNode == null)
                printNode = current;

            if(prevBeginNode == null) {
                prevBeginNode = beginNode;
            } else {
                prevBeginNode.nextAddress = current.address;
                prevBeginNode = beginNode;
            }

            if(next == null) {
                beginNode.nextAddress = "-1";
                break;
            }

            beginNode.nextAddress = next.address;
            prev = next;
            current = prev.next(nodes);
            next = current.next(nodes);
            beginNode = prev;

            validenodeNum -= K;
        }

        while(printNode != null) {
            System.out.println(printNode);
            printNode = printNode.next(nodes);
        }


    }

    static class Node {

        String address = "";
        int data = 0;
        String nextAddress = "";

        public Node(String address, int data, String nextAddress) {
            this.address = address;
            this.data = data;
            this.nextAddress = nextAddress;
        }

        @Override
        public String toString() {
            return address + " " + data + " " + nextAddress;
        }

        public Node next(HashMap<String, Node> nodes) {
            return nodes.get(nextAddress);
        }
    }

}

#include <iostream>
#include <stack>
#include <iomanip>
using namespace std;
struct node
{
     int x;       //记录下当前的序号
     int next;   //记录下下一个节点的地址
     int index;   //记录下当前的地址
};
 
 int main()
 {
     node list_ans[100000];   //以数组来作为数据结构承载链表
     int first_add = 0, N = 0, K = 0, temp_address = 0;
     int i = 0, j = 0, k = 0;
     stack<node> sta;
     cin >> first_add >> N >> K;
     for (i = 0; i < N; i++)                         //输入数据
     {
         cin >> temp_address;
         list_ans[temp_address].index = temp_address;
         cin >> list_ans[temp_address].x;
        cin >> list_ans[temp_address].next; 
     }
     int  pre = first_add;  //检查数据长度，链表的总长度（坑点不一定为N）
     while (pre != -1)
     {
         k++;
         pre = list_ans[pre].next;
     }
     N = k;       //更新N
     pre = first_add;
     int res = N % K, iter = N / K;   //计算需要翻转的次数，以及最后会剩下多少数
     bool first = true;     
     node temp_node;
     for (i = 0; i < iter; i++)    //需要进行翻转次数的计数
     {
         for (j = 0; j < K; j++)   //从起始地址开始进行入栈操作，进入K个
         {
             sta.push(list_ans[pre]);   
             pre = list_ans[pre].next;
         }
         while (!sta.empty())
         {
             temp_node = sta.top();    //出栈操作，第一个出栈的与后序出栈的操作不同，分开处理
             sta.pop();
             if (first)
             {
                 cout << setfill('0') << setw(5) << temp_node.index << " " << temp_node.x;   
                 first = false;
            }
             else
             {
                 cout << " " << setfill('0') << setw(5) << temp_node.index << endl;
                 cout << setfill('0') << setw(5) << temp_node.index << " " << temp_node.x;
             }
         }
      }
      //非翻转的数据进行如下的顺序输出即可
      for (j = 0; j < res; j++)
      {
          temp_node = list_ans[pre];
          pre = list_ans[pre].next;
          if (first)
         {
             cout << setfill('0') << setw(5) << temp_node.index << " " << temp_node.x; 
            first = false;
        }
         else
         {
            cout << " " << setfill('0') << setw(5) << temp_node.index << endl;
            cout << setfill('0') << setw(5) << temp_node.index << " " << temp_node.x;
         }
      }
      //最后补上空格和 -1 的操作
      cout << " " << -1;
      return 0;
 }
 

//两个用例通不过，求大神指导
#include <stdio.h>
typedef struct {
    int data;
    int next;
} Node;
int Reverse(Node *a, int head, int K);
int main()
{
    Node a[100002]={0};
    int N;
    int N1;
    int K;
    int adress;
    int data;
    int next;
    int i;
    int flag = 0;
    int cnt = 0;
    int head;
    int hTmp;
    int count=1;
    scanf("%d %d %d", &hTmp, &N, &K);
    int h = hTmp;
    for(i=0;i<N;i++)
    {
        scanf("%d %d %d", &adress, &data, &next);
        a[adress].data = data;
        a[adress].next = next;
    }
    for(;a[h].next!=-1;)
    {  count++;  h = a[h].next;  }  N = count;  N1 = count;
    while(N>=K)
    {
        hTmp = Reverse(a, hTmp, K);
        if(cnt!=0)
        {  a[flag].next = hTmp;  }  if(cnt==0)
        {  head = hTmp;  }
        cnt++;  for(i=0;i<K;i++)   {    if(i==K-1)    {    flag=hTmp;  }   hTmp = a[hTmp].next;   }
        N-=K;
    }
    
      for(i=0;i<N1;i++)   {   if(a[head].next!=-1)  {  printf("%05d %d %05d\n", head, a[head].data, a[head].next);  }  else  {  printf("%05d %d %d\n", head, a[head].data, a[head].next);  }   head = a[head].next;   }
    return 0;
}
int Reverse(Node *a, int head, int K)
{
    int cnt = 1;
    int tmp;
    int new_ = head;
    int old = a[new_].next;
    while(cnt < K)
    {
        tmp = a[old].next;
        a[old].next = new_;
        new_ = old;
        old = tmp;
        cnt++;
    }
    a[head].next = old;
    return new_;
}

#include<bits/stdc++.h>
using namespace std;
struct lian{
	string address,next;
	long long data;
}s1[100001],s2[100001];

int main(){
	string str;
	int n,k;
	cin>>str>>n>>k;
	int i,l;
	int j=0;
	for(i=0;i<n;i++)cin>>s1[i].address>>s1[i].data>>s1[i].next;
	for(i=0;i<n;i++){
		if(s1[i].address==str){
			s2[j].address=s1[i].address;s2[j].data=s1[i].data;s2[j].next=s1[i].next;break;
		}
	}
	while(s2[j].next!="-1"){
		for(i=0;i<n;i++){
			if(s1[i].address==s2[j].next){
				j++;s2[j].address=s1[i].address;s2[j].data=s1[i].data;s2[j].next=s1[i].next;break;
			}
		}
	}
	j++;
	for(i=k-1;i<j-j%k;i+=k){
		if(i==k-1)cout<<s2[i].address<<' '<<s2[i].data;
		else cout<<' '<<s2[i].address<<"\n"<<s2[i].address<<' '<<s2[i].data;
		for(l=1;l<k;l++){
			cout<<' '<<s2[i-l].address<<"\n"<<s2[i-l].address<<' '<<s2[i-l].data;
		}
	}
	if(j<k){
		for(i=0;i<j;i++){
			cout<<s2[i].address<<' '<<s2[i].data<<' '<<s2[i].next<<endl;
		}
	}
	else {
		for(i=j-j%k;i<j;i++){
			cout<<' '<<s2[i].address<<"\n"<<s2[i].address<<' '<<s2[i].data;
		}
		cout<<" -1"<<endl;
	}
}

//感觉思路挺清晰的
#include<iostream>
using namespace std;
int head, N, K, newStart;
struct LNode{
	int Data; 
	int Next;
}L[100000];

void Reverse(LNode *node, int &head, int k){
	int cnt = 0;			
	int	preLastNode = -1;				//表示前一段待反转区段的最后一个结点 
	int p = head, first, pre, cur, nex;
	while(p != -1){
		cnt++;
		int tmp = node[p].Next;			//记录当前结点的下一个结点，将来反转后的尾结点要指向tmp 
		if( cnt == 1 )					//first为当前反转段的第一个元素
			first = p;			
		if( cnt == k ){
			pre = tmp, cur = first, nex; 
			while(cnt){					//反转cnt次 
				nex = L[cur].Next;
				L[cur].Next = pre;
				pre = cur;
				cur = nex;
				cnt--; 	
			}
			//这里的p为反转后在反转区段中的头结点 
			if( preLastNode == -1)		//第一次反转的时候，需要做特殊处理，将head改变为当前的结点 
				head = p;
			else						//将前一次反转的最后一个结点指向当前结点,防止断链 
				node[preLastNode].Next = p;
			preLastNode = first;	 	 
		}
		p = tmp;						//这里 p = L[p].Next会陷入死循环，因为已经实现反转了  
	}
} 
int main(void){
	scanf("%d %d %d", &head, &N, &K);
	int Address, Data, Next;
	for(int i = 0; i < N; i++){
		scanf("%d %d %d", &Address, &Data, &Next);
		L[Address].Data = Data;
		L[Address].Next = Next;
	}
	int flag = 0;
	Reverse(L, head, K);
	int p = head;
	while(p != -1){
		if(L[p].Next != -1)printf("%05d %d %05d\n", p, L[p].Data, L[p].Next);
		else  printf("%05d %d %d\n", p, L[p].Data, L[p].Next);
		p = L[p].Next;
	}
}

#include <stdio.h>

struct node {
	int data, next;
};

int list_reverse(struct node *nodes, int head, int k)
{
	int i, p, new_head, tmp_head;

	for(i = 0, p = head; i < k && p != -1; ++i, p = nodes[p].next)
		;

	if(i < k)
		return head;

	for(i = 0, new_head = -1, tmp_head = head; i < k; ++i) {
		p = tmp_head;
		tmp_head = nodes[tmp_head].next;

		nodes[p].next = new_head;
		new_head = p;
	}

	nodes[head].next = list_reverse(nodes, tmp_head, k);

	return new_head;
}

int main()
{
	int head, n, k, i, addr;
	struct node nodes[100000] = {{0}};

	scanf("%d%d%d", &head, &n, &k);

	for(i = 0; i < n; ++i) {
		scanf("%d", &addr);
		scanf("%d%d", &nodes[addr].data, &nodes[addr].next);
	}

	head = list_reverse(nodes, head, k);

	for(i = head; nodes[i].next != -1;i = nodes[i].next)
		printf("%05d %d %05d\n", i, nodes[i].data, nodes[i].next);

	printf("%05d %d -1\n", i, nodes[i].data);

	return 0;
}

A, B, C = input().split()
B, C = eval(B), eval(C)
L = [input().split() for i in range(B)]
D = {i[0]:i for i in L}
p = A
L = [D[p]]
while D[p][2] != '-1':
    p = D[p][2]
    L.append(D[p])
L = [i[0] for i in L]
L = [L[i:i+C] for i in range(0, len(L), C)]
L = [reversed(i) if len(i) == C else i for i in L]
L = ' '.join([' '.join(i) for i in L]).split()
L = [D[i] for i in L]
for i, j in enumerate(L):
    j[2] = L[i + 1][0] if i != len(L) - 1 else '-1'
for i in L:
    print(' '.join(i))

参考了前面的几个朋友的回答，想明白了有几个坑：

1.虽然给定了总节点数N，但不是所有的节点都连在链表上，有很多废节点。

2.链表上的有效节点数num需要自己统计。

3.题目中只给定了K<=N,但N并不是有效节点数，所以存在K>有效节点数num，链表不需要翻转的情况。（感觉这里有点故意干扰你的意思）

解决思路：

构造一个新的链表(只需记录头尾则可)，从头开始遍历原链表，每次构造一个长度为k的小链表，加入到新链表中，期间记录遍历的节点数目，最后不满足k个节点时，直接将节点连入新链表中则可。

#include <stdio.h>

struct Node
{
    int data;
    int next;
};

Node a[100010];

int main()
{
    int n;
    int k;
    int first_add;

    scanf("%d%d%d", &first_add, &n, &k);

    int t_add;
    int t_data;
    int t_next;

    for(int l = 0; l< n; l++)
    {
        scanf("%d%d%d", &t_add, &t_data, &t_next);
        a[t_add].data = t_data;
        a[t_add].next = t_next;
    }

    //num 用于计算链表中的有效节点数目 
    int num = 0;
    int e = first_add;
    while(e!= -1)
    {
        e= a[e].next;
        num ++;
    }

    //i记录已经连到全局新链表中的节点的数目 
    int i = 0;

    //p用于遍历链表 
    int p = first_add;

    //l_head , l_tire指向全局新链表的头和尾，
    //初始时没有节点，均赋值为-2 
    int l_head = -2;
    int l_tire = -2;

    while(p!= -1)
    {
        //如果有效节点数 < k, 则整个链表无需翻转，直接给l_head赋值则可 
        if(num < k)
        {
            l_head = p;
            break;
        }

        //需要翻转，这里是到最后，剩余节点数目少余k个，将节点直接接在全局新链表则可。 
        if(num - i < k)
        {
            //后面直接连上
            a[l_tire].next = p;

            break;
        }

        //else
        //否则长度大于k，构造一个长度为k的翻转的链表，t_head,t_tire指向头尾，将其连接在全局链表的后面 
        int t_head = p;
        int t_tire = p;

        int q = a[p].next;
        a[p].next = -1;

        for(int m = 0; m<k-1; m++)
        {
            int tmp = a[q].next;
            a[q].next = t_head;
            t_head = q;

            q= tmp;
        }

        //加入全局新链表 
        if(l_tire == -2)
        {
            l_tire = t_tire;
        }
        else
        {
            a[l_tire].next = t_head;
            l_tire = t_tire;
        }

        if(l_head == -2)
        {
            l_head = t_head;
        }

        //p后移，i表示已经加入链表中的节点数，+k 
        p = q;
        i = i + k;
    } 

    //从l_head输出新链表 
    int w = l_head;
    while(w!=-1)
    {
        if(a[w].next != -1)
            printf("%05d %d %05d\n", w, a[w].data, a[w].next);
        else
        {
            printf("%05d %d %d\n", w, a[w].data, a[w].next);
        }
        w = a[w].next;
    }

    return 0;
}

out = []
lst = [None for i in range(100001)]
st,num,k = map(int,input().split()) 
for i in range(num):
    t = list(map(int,input().split()))
    lst[t[0]] = [t[1],t[2]]
while st!=-1:
    out.append([st,lst[st][0]])
    st = lst[st][1]
time = len(out)//k
for i in range(time):
    te = out[i*k:i*k+k]
    te.reverse()
    out[i*k:i*k+k] = te
for i in range(len(out)-1):
    print("%05d"%out[i][0]+" "+str(out[i][1])+" "+"%05d"%out[i+1][0])
print("%05d"%out[len(out)-1][0]+" "+str(out[len(out)-1][1])+" "+"-1")

#include <bits/stdc++.h>
using namespace std;

#define MAXSIZE 100005   //最大为五位数的地址

struct LinkNode   //使用顺序表存储数据data和下一地址next
{
   int data;
   int next;
};

int main()
{
    vector<LinkNode> v(MAXSIZE);
    int Head, N, K;
    cin >> Head >> N >> K;   //输入头地址 和 N,K
    for (int i = 0; i < N; i++)
    {
        int temp;   //用来存放结点地址的临时变量
        cin >> temp;   //这里不能和下一行写成一行,一定要先读取完temp
        cin >> v[temp].data >> v[temp].next;
    }
    int count = 0;  //count用来存储能够首尾相连的节点数
    int p = Head;   //p指示当前结点
    int List[MAXSIZE];   //存储可以连接上的顺序表
    while(p != -1)
    {
        List[count++] = p;
        p = v[p].next;
    }
    for (int i = 0; i + K <= count; i += K)  //每K个节点做一次翻转
    {
        reverse(&List[i],&List[i+K]);
    }
    for (int i = 0; i < count-1; i++)
    {
        printf("%05d %d %05d\n",List[i],v[List[i]].data,List[i+1]);
    }
    printf("%05d %d -1\n",List[count-1],v[List[count-1]].data);
    return 0;
}