首页 > 试题广场 >

反转链表 (25)

[编程题]反转链表 (25)
  • 热度指数:26480 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 146M,其他语言293M
  • 算法知识视频讲解
给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。例如:给定L为1→2→3→4→5→6,K为3,则输出应该为
3→2→1→6→5→4;如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。 

输入描述:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N),即要求反转的
子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。


输出描述:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
示例1

输入

00100 6 4<br/>00000 4 99999<br/>00100 1 12309<br/>68237 6 -1<br/>33218 3 00000<br/>99999 5 68237<br/>12309 2 33218

输出

00000 4 33218<br/>33218 3 12309<br/>12309 2 00100<br/>00100 1 99999<br/>99999 5 68237<br/>68237 6 -1
package pat.t0905;

import java.util.*;

public class T1015 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Map<String, Node> map = new HashMap<>();
		String beginAddr = sc.next();// 首地址
		int nodeCount = sc.nextInt();// 节点总数
		int groupSize = Integer.parseInt(sc.nextLine().trim());
		for (int i = 0; i < nodeCount; i++) {
			String[] line = sc.nextLine().split(" ");
			Node node = new Node(line[0], line[1], line[2]);
			map.put(line[0], node);
		}
		String addr = beginAddr;
		List<Node> list = new ArrayList<>();
		while (!"-1".equals(addr)) {
			Node node = map.get(addr);
			if (node == null) {
				break;
			}
			addr = node.next;
			list.add(node);
		}
		List<Node> list2 = new ArrayList<>();// 排序好存在新列表中
		for (int i = 1; i * groupSize <= list.size(); i++) {
			for (int j = 0; j < groupSize; j++) {
				list2.add(list.get(i * groupSize - j - 1));
			}
		}
		int rest = list.size() % groupSize;
		for (int i = list.size() - rest; i < list.size(); i++) {
			list2.add(list.get(i));
		}
		for (int i = 0; i < list2.size() - 1; i++) {
			list2.get(i).next = list2.get(i + 1).address;
		}
		list2.get(list2.size() - 1).next = "-1";
		for (Node node : list2) {
			System.out.println(node);
		}
		sc.close();
	}
}

class Node {
	String address;
	String data;
	String next;

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

	public String toString() {
		return address + " " + data + " " + next;
	}
}

1.用Map<节点地址,节点>存储数据,
2.用List按连接顺序取出,
3.用新的List存储处理后的节点数据。
发表于 2019-09-05 21:57:01 回复(0)
TMD,这题真坑,看完题目立马有思路,写完代码死活AC不过,一直提示越界,后来看了讨论区才发现,TM有无效结点,实际结点会小于输入的n,草。前前后后磨蹭了近4小时,一下午就在这弄这题,***了。
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);
            }            
    }
}


发表于 2019-08-17 18:26:49 回复(1)

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

  • 题目输入可能包含无效节点,你需要自行遍历一遍链表来确定节点的真实数量
  • 有效节点数可能小于 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);
        }
    }

}
发表于 2019-06-22 22:37:34 回复(0)

//注意:输入的可能不止一个链表!!!即N不一定是需要反转链表的长度
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String firstAddress = scanner.next();
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        if (N > 100000) N = 100000;
        HashMap<String, String> addressmap = new HashMap<>();
        HashMap<String, String> datamap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String address = scanner.next();
            String data = scanner.next();
            String next = scanner.next();
            addressmap.put(address, next);
            datamap.put(address, data);
        }
        List<String> addressList = new ArrayList<>();
        String address = firstAddress;
        while (!address.equals("-1")) {
            addressList.add(address);
            address = addressmap.get(address);
        }
        int len=addressList.size();
        int count = len / K;
        String[][] res = new String[len][2];
        int num = 0;
        while (count > 0) {
            int p = num;
            for (int i = num + K - 1; i >= num; i--) {
                String addr = addressList.get(i);
                res[p][0] = addr;
                res[p][1] = datamap.get(addr);
                p++;
            }
            num += K;
            count--;
        }
        for (int j = num; j < len; j++) {
            String addr = addressList.get(j);
            res[j][0] = addr;
            res[j][1] = datamap.get(addr);
        }
        for (int x = 0; x < len- 1; x++) {
            System.out.println(res[x][0] + " " + res[x][1] + " " + res[x + 1][0]);
        }
        System.out.println(res[len- 1][0] + " " + res[len- 1][1] + " -1");
    }
}




编辑于 2018-11-30 15:54:10 回复(0)
package pat15;


import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner input=new Scanner(System.in);
	Node n=null;
	int first=input.nextInt();
	int count=input.nextInt();
	int size=input.nextInt();
	Node[] nrr=new Node[100002];
	nrr[100001]=new Node(0, 0, first);
	int ad=0;
	int data=0;
	int next=0;
	int arr=0;
	for(int i=0;i<count;i++){
		ad=input.nextInt();
		data=input.nextInt();
		next=input.nextInt();
		if(ad<1000000 && next <1000000){
			nrr[ad]=new Node(ad, data, next);
			arr++;
		}
	}
	int j=0;
	int i=100001;
	for(j=arr/size;j>0 && i!=-1;j--)
		i=reverse(nrr,i,size);

	String nt="";
	String nts="";
	int key=nrr[100001].next;
	while(key!=-1){
		n=nrr[key];
		nt=tackbak(n.ad);
		nts=tackbak(n.next);
		System.out.println(nt+" "+n.data+" "+nts);
		key=nrr[key].next;
	}
		
}
private static int reverse(Node[] nrr, int head, int size) {
	int wei=nrr[head].next;
	int oldone=nrr[head].next;
	int p=0;
	//尾
	for(int j=0;j<size && wei!=-1;j++ ){
		wei=nrr[wei].next;
	}
	nrr[head].next=wei;
	for(int j=0;j<size  && oldone!=-1;j++){
		p=nrr[oldone].next;
		nrr[oldone].next=nrr[head].next;
		nrr[head].next=oldone;
		oldone=p;
	}
	return oldone;
	
}
private static String tackbak(int ad) {
	String str=ad+"";
	if(ad!=-1){
		
	while(str.length()<5)
		str="0"+str;}
	return str;
}
}
class Node{
	public int ad;
	public int data;
	public int next;
	public Node(int	 ad, int data, int next) {
		super();
		this.ad = ad;
		this.data = data;
		this.next = next;
	}		
}
内存超限超限,心态崩了,弃题。
发表于 2017-08-20 16:08:52 回复(0)
import java.util.HashMap; import java.util.Scanner;  public class Main { public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  String[] fline = sc.nextLine().split(" ");  //因为结点不是按顺序输入,哈希表用来辅助建造链表  HashMap<String, Node> map = new HashMap<>();  //root作为头结点  Node root = new Node(null, null);  root.ad = "first";  Node n = new Node(fline[0], null);  root.next = n;  map.put("first",root);  map.put(fline[0], n);  int N = Integer.parseInt(fline[1]);  int K = Integer.parseInt(fline[2]);  //构建链表  for (int i = 0; i < N; i++) {
            String[] line = sc.nextLine().split(" ");  Node node;  Node next = null;  if (map.containsKey(line[0])) {
                node = map.get(line[0]);  } else {
                node = new Node(line[0], null);  } if (!line[2].equals("-1")) { if (map.containsKey(line[2])) {
                    next = map.get(line[2]);  } else {
                    next = new Node(line[2], null);  }
            }
            node.next = next;  node.data = line[1];  map.put(line[0], node);  map.put(line[2], next);  } //遍历链表进行翻转  Node p = root.next;  Node pre = root;  Node temp = null;  int count = 0;  while (p != null) {
            count ++;  Node pnext = p.next;  p.next = temp;  temp = p;  if (count == K) {
                count = 0;  Node q = pre.next;  pre.next = temp;  q.next = pnext;  temp = null;  pre = q;  }
            p = pnext;  }
        pre.next = null;  if (temp != null) {
            p = temp;  while (p != null) {
                temp = p.next;  p.next = pre.next;  pre.next = p;  p = temp;  }
        } //遍历链表进行输出  p = root.next;  while (p != null) {
            Node next = p.next;  System.out.print(p.ad + " " + p.data + " ");  if (next != null) {
                System.out.println(next.ad);  } else {
                System.out.println("-1");  }
            p = next;  }


    }
} class Node { Node(String ad, Node next) { this.ad = ad;  this.next = next;  }
    String data = null;  String ad = null;  Node next = null;  }
发表于 2017-01-26 14:31:12 回复(1)