投稿
  1. 首页
  2. python

基于Java开发一套完整的区块链系统（附完整源码）

code • 2022-4-27 • python • 阅读 105

基于Java开发一套完整的区块链系统（附完整源码）,第1张

前言

近几年区块链概念越来越火，特别是区块链技术被纳入国家基础设施建设名单后，各大企业也开始招兵买马，对区块链技术进行研究，从各大招聘网站的区块链职位来看，薪资待遇都很不错，月薪30K到80K的都有，这对于我们程序员来说也是一种机遇，说明学习区块链技术刻不容缓。

这套区块链系统代码非常简洁清晰，对于新手来说非常好理解，旨在告诉大家其实区块链技术并没有那么高深复杂。系统中除了springboot框架外，其他基本都是纯原生开发，就连P2P网络也是用的java socket来实现的。

一、区块链技术理论基础 1、基本概念 （1）区块链

从技术层面来看，区块链是由包含交易信息的区块按照时间顺序从后向前有序链接起来的数据结构。

从应用层面来说，区块链是一个分布式的共享账本和数据库，具有去中心化、不可篡改、全程留痕、集体维护、公开透明等特点。基于这些特点，区块链技术可以开发出自带信任体系特征的系统，实现多个主体之间的协作信任与一致行动。

区块是区块链中的最小组成单位，主要有包含元数据的区块头和存放一条或者多条交易信息的区块体两部分组成，每个区块都记录着当前区块的哈希和上一个区块的哈希，通过两个哈希值的关联，让所有的区块以链式结构串起来，就形成了一个完整的区块链。

区块链中的第一个区块被称作为创世区块，无需关联上一个区块。以BTC网络为例，每个区块主要包含如下信息字段：

  • 区块大小：用字节表示的区块数据大小
  • 区块头：组成区块头的包括以下几个字段：
    1. 区块头hash值2. 父区块头hash值3. 时间戳：区块产生的近似时间4. Merkle根：该区块中交易的merkle树根的哈希值5. 难度目标：该区块工作量证明算法的难度目标6. Nonce：用于工作量证明算法的计数器
  • 交易计数器：交易的数量
  • 交易：记录在区块里的交易信息

区块链结构的简易模型，如下图所示：


区块中的交易集合记录的是一些特定的信息，在BTC网络中主要记录的是交易信息，在其他区块链网络中可以按照业务逻辑来保存相应的业务数据，如审计信息、版权信息、票据信息等，这也是区块链经常用来当做共享账本的原因。

打个比方，可以把区块链当做一个用来记账的笔记本，一个区块就相当于一页纸，上面记录了某一时间段內所有的账务信息，从第一页到最后一页，按照页码顺序排列起来就是一个完整的账本。

（2）区块链网络

实际的区块链系统由多个区块链节点组成，每个节点都运行着相同一套区块链主干网络的副本，且各个节点间通过P2P网络进行交互，并最终形成一个完整的区块链网络系统。

P2P网络具有可靠性、去中心化，以及开放性，各个节点之间交互运作、协同处理，每个节点在对外提供服务的同时也使用网络中其他节点所提供的服务。当某一个区块链节点产生新的区块时，会通过广播的方式告诉其他节点，其他节点通过网络接收到该区块信息时，会对这个区块信息进行验证，当有一定数量的节点都验证通过后，各个节点会把该区块更新到各自现有的区块链上，最终使得整个区块链网络中的各个节点信息保持一致，这也是区块链去中心化、可信任特性的体现。

区块链网络简易模型，如下图所示：

2、区块链分类 （1）公有链

公有区块链（Public Block Chains)是指：世界上任何个体或者团体都可以发送交易，且交易能够获得该区块链的有效确认，任何人都可以参与使用和维护该区块链，信息公开透明。公有区块链是最早的区块链，例如BTC、以太坊等虚拟数字货币均基于公有区块链。不过目前公有链实际应用价值不大，并没有产生特别合适的应用场景。

（2）联盟链

行业区块链（Consortium Block Chains)：由某个群体内部指定多个预选的节点为记账人，每个块的生成由所有的预选节点共同决定（预选节点参与共识过程），其他接入节点可以参与交易，但有权限限制，信息受保护，如银联组织。目前联盟链是各个区块链技术团队主要研究的对象，由于联盟链拥有区块链技术的大部分特征，并且在权限管理、数据安全、监管方面更有优势，是企业优先考虑的区块链技术方案。

市面上也有一些比较主流的联盟链技术框架，让开发维护联盟链更加便捷。国内一些大的软件厂商也都有自己的企业区块链技术解决方案，例如蚂蚁金服区块链平台，腾讯的TrustSQL平台，东软的SaCa EchoTrust区块链应用平台以及京东区块链防伪追溯平台等等。

（3）私有链

私有区块链（Private Block Chains)：仅仅使用区块链的总账技术进行记账，可以是一个公司，也可以是个人，独享该区块链的写入权限，利用区块链的不易篡改特性，把区块链作为账本数据库来使用。

3、关键技术与特性 （1）共识机制

共识机制被称作为区块链系统的灵魂，是区块链系统信任体系的基础。区块链系统作为一个多节点的分布式账本系统，当有新的信息需要记录时，哪个节点来负责记账，记账奖励发放给哪个节点，哪些节点负责验证记账结果，如何让各个节点达成最终一致，将记账结果被网络中所有节点以同样的顺序复制并记录下来，就是共识机制要做的事情。

而按照百度百科上的说法：

所谓“共识机制”是通过特殊节点的投票，在很短的时间内完成对交易的验证和确认，对一笔交易，如果利益不相干的若干个节点能够达成共识，我们就可以认为全网对此也能够达成共识。再通俗一点来讲，如果中国一名微博大V、美国一名虚拟币玩家、一名非洲留学生和一名欧洲旅行者互不相识，但他们都一致认为你是个好人，那么基本上就可以断定你这人还不坏。

目前，较为主流的共识算法有PoW、PoS、DPoS、PBFT等，在实际使用时，每种算法都有各自的优点和缺点。在应用于不同场景时，区块链项目将会采用不同的共识机制和算法。

（2）去中心化

去中心化，是互联网发展过程中形成的社会关系形态和内容产生形态，是相对于“中心化”而言的新型网络内容生产过程。在一个分布有众多节点的区块链系统中，每个节点都具有高度自治的特征。任何一个节点都可能成为阶段性的中心，但不具备强制性的中心控制功能。节点与节点之间的影响，会通过网络而形成关联关系。这种开放式、扁平化、平等性的系统现象或结构，我们称之为去中心化。

去中心化的系统具有容错力高、抗攻击力强的特征。中心化的系统一旦中心出现问题，整个系统都会崩溃，但是区块链系统中的任何一个节点出现问题，并不会对整个区块链网络产生太大的影响。

另外，去中介化并不代表着不接受监管，“去中心化”去的是中央控制方和中介方，而不是监管方。监管节点可以方便地接入任何一个区块链网络。并且由于区块链的公开透明特性，监管机构反而可以更加方便地监控整个系统的交易数据。

（3）智能合约

从技术层面讲，智能合约是一段部署在在区块链上的程序代码，当满足程序设定的条件时，它便会在区块链上运行，并得到相应的结果。这种情况有点类似于微信的小程序，区块链提供虚拟机和脚本语言，用户根据脚本语言的语法开发带有一定业务逻辑的程序，部署在区块链上，当满足执行的条件时，智能合约便会被区块链虚拟机解释并运行。

典型的应用便是以太坊平台的智能合约，在这个平台里可以支持用户通过简单的几行代码就能实现他们想要的合约，实现无需人为监督的、不可篡改、自动化运行的合约，买卖房子不需要再找中介、借钱不需要再找公证人……人们可以随时随地根据自身需求发起合约，它的执行不依赖某个人和组织，所有的信任完全基于以太坊区块链平台本身。

（4）不可篡改性

大部分人习惯称它为不可篡改性，但是从技术层面来说，我个人觉得叫做不可逆转性更贴切，既然是一个计算机系统，增删改查是基本的功能属性，只不过区块链系统删除和修改 *** 作比较特殊一点。

区块链是由每个区块的哈希值串连起来的链式结构，而区块的哈希值=SHA256(“当前区块内容+上一个区块的哈希值”)，任何一个区块的内容发生修改，都会引起哈希值的变化，而哈希值的变化也会引起子区块哈希值发生变化，进而引起整个区块链的改变。

因此任何人想要修改区块的数据几乎是不可能的，除非他把整个区块链中从创世区块到最新的区块的所有哈希值全部重新修改一遍，并且修改完之后，还得广播告诉网络中的其他所有节点，让其他所有节点接受修改。

不过按照目前计算机的算力，想要在短时间内从区块链头部到尾部全部修改一遍，是一件非常困难的事，并且即使修改完了，其他节点也不会接受修改，因为凭一己之力，没有能够让所有节点达成共识的条件。

4、流行的区块链框架与应用 （1）公有链应用：BTC网络

区块链1.0产品，对于比特币，中本聪是这样定义的：是一种完全通过点对点技术实现的电子现金系统，它使得在线支付能够直接由一方发起并支付给另外一方，中间不需要通过任何的金融机构。

与所有的货币不同，比特币不依靠特定货币机构发行，它依据特定算法，通过大量的计算产生，比特币经济使用整个P2P网络中众多节点构成的分布式数据库来确认并记录所有的交易行为，并使用密码学的设计来确保货币流通各个环节安全性。之后人们根据比特币网络技术整理出了区块链技术体系，去解决信任的问题，而比特币网络原理也成为了区块链技术初学者的经典教材。

（2）公有链应用：以太坊网络

区块链2.0产品的代表，以太坊是一个为去中心化应用（Dapp）而生的开源区块链平台，拥有着大部分区块链技术的特征，但与其它区块链不同的是，以太坊是可编程的，开发者可以用它来构建不同的应用程序，通过其专用加密货币以太币（简称“ETH”）提供去中心化的以太虚拟机（Ethereum Virtual Machine）来处理点对点合约（就是一些脚本程序代码）。如果把比特币网络看作是一套分布式的数据库，而以太坊则更进一步，它可以看作是一台分布式的计算机：区块链是计算机的ROM，合约是程序，而以太坊的矿工们则负责计算，担任CPU的角色。


以太坊的概念首次在2013至2014年间由程序员Vitalik Buterin受比特币启发后提出，大意为“下一代加密货币与去中心化应用平台”。虽然以太坊作为平台可以在其上开发新的应用，但是由于以太坊的运行和BTC网络一样，采用的是Token机制，且平台性能不足，经常出现网络拥堵的情况，平台用来学习开发与测试区块链技术还可以，用于实际生产的话不太现实。

（3）联盟链开发框架：Hyperledger Fabric

Hyperledger Fabric 也叫超级账本，它是 IBM 贡献给 Linux 基金会的商用分布式账本，是面向企业应用的全球最大的分布式开源项目。像其他区块链技术一样，它也有一个账本，可以使用智能合约。Fabric的智能合约可以有多种架构，它可以用主流语言编程，例如Go、Java和Javascript，此外也可以使用Solidity。

至今，Fabric已获得了阿里巴巴、AWS、Azure、百度、谷歌、华为、IBM、甲骨文、腾讯等互联网巨头的支持。许多企业的区块链平台都把Fabric作为底层框架来使用，例如甲骨文。不过由于IBM对区块链的定义强调了区块链的分布式和不可变两个元素，对共识机制进行了削弱，采用了Kafka和zookeeper的“排序服务”实现共识，因此部分业内人士也称超级账本是“伪区块链”，但是即便如此，也抵挡不了企业对超级账本的喜爱，目前Fabric 2.0版本已经正式发布。

（4）小结

目前公有链在实际应用中并没有太多的业务场景落地，大部分都是以挖矿为主题或者线上宠物饲养的游戏为主，并且由于数字货币的匿名性，有些不法分子利用这一特点，将数字货币用于洗钱、暗网买卖等违法行为，是各个国家的打击对象，我国政策法规也严厉禁止，因此对于技术人员来说，公有链可以作为研究学习的对象，其他方面暂时没有太多实际意义。

目前大部分区块链企业的研究方向主要是针对企业的联盟链和私有链，并且国家层面也在大力支持区块链技术的发展，特别是区块链底层核心技术的研发，倡导把区块链作为核心技术自主创新的重要突破口，明确主攻方向，加大投入力度，着力攻克一批关键核心技术，加快推动区块链技术和产业创新发展。不过现在市面上主流的区块链平台大部分还是以国外公司主导的为主，国内区块链底层核心技术的发展，还需要技术人员的加倍努力。

二、区块链技术Java实现 1、区块链技术架构


目前主流的区块链技术架构主要分为五层，数据层是最底层的技术，主要实现了数据存储、账户信息、交易信息等模块，数据存储主要基于Merkle树，通过区块的方式和链式结构实现，而账户和交易基于数字签名、哈希函数和非对称加密技术等多种密码学算法和技术，来保证区块链中数据的安全性。

网络层主要实现网络节点的连接和通讯，又称点对点技术，各个区块链节点通过网络进行通信。共识层是通过共识算法，让网络中的各个节点对全网所有的区块数据真实性正确性达成一致，防止出现拜占庭攻击、51攻击等区块链共识算法攻击。

激励层主要是实现区块链代币的发行和分配机制，是公有链的范畴，我们不做分析。应用层一般把区块链系统作为一个平台，在平台之上实现一些去中心化的应用程序或者智能合约，平台提供运行这些应用的虚拟机。

接下来我们基于Java语言来开发一套小型的区块链系统，来实现数据层、网络层、共识层的一些功能，用简单的代码来直观抽象的概念，以便加深对以上区块链技术基础理论的理解。

2、基于java的区块链开发实战 （1）开发环境

开发工具

VSCode

开发语言

Java

JDK版本

JDK1.8或者OpenJDK11

开发框架

SpringBoot2.2.1

工程管理

Maven3.6

测试工具

Postman

（2）区块链基本模型构建

区块是区块链系统的最小单元，第一步我们先实现最简单的区块结构，新建Block.java类，主要包含以下几个字段：
Block.java

/**
 * 区块结构
 * 
 * @author Jared Jia
 *
 */
public class Block implements Serializable {


  private static final long serialVersionUID = 1L;
  /**
   * 区块索引号(区块高度)
   */
  private int index;
  /**
   * 当前区块的hash值,区块唯一标识
   */
  private String hash;
  /**
   * 前一个区块的hash值
   */
  private String previousHash;
  /**
   * 生成区块的时间戳
   */
  private long timestamp;
  /**
   * 工作量证明，计算正确hash值的次数
   */
  private int nonce;
  /**
   * 当前区块存储的业务数据集合（例如转账交易信息、票据信息、合同信息等）
   */
  private List transactions;
  
  /*** 省略get set方法****/
  }

区块链是由区块按照区块哈希前后顺序串联起来的数据结构，哈希值通过散列算法对区块进行二次哈希计算而得到的数字摘要信息（不了解散列函数的，可以先百度了解一下SHA算法），用于保证区块的信息安全以及整条区块链的有效性。因此第二步我们新增计算区块Hash值的方法，采用SHA256算法，通过java实现：
CryptoUtil.java

/**
 * 密码学工具类
 * 
 * @author Jared Jia
 *
 */
public class CryptoUtil {


  /**
   * SHA256散列函数
   * @param str
   * @return
   */
  public static String SHA256(String str) {
    MessageDigest messageDigest;
    String encodeStr = "";
    try {
      messageDigest = MessageDigest.getInstance("SHA-256");
      messageDigest.update(str.getBytes("UTF-8"));
      encodeStr = byte2Hex(messageDigest.digest());
    } catch (Exception e) {
      System.out.println("getSHA256 is error" + e.getMessage());
    }
    return encodeStr;
  }
  
  private static String byte2Hex(byte[] bytes) {
    StringBuilder builder = new StringBuilder();
    String temp;
    for (int i = 0; i < bytes.length; i++) {
      temp = Integer.toHexString(bytes[i] & 0xFF);
      if (temp.length() == 1) {
        builder.append("0");
      }
      builder.append(temp);
    }
    return builder.toString();
  }
}

第三步，创建一个链式结构对象，按照先后顺序来保存区块对象，从来形成一个有序的区块链表，考虑到线程安全问题，采用CopyOnWriteArrayList来实现，为了方便测试，暂且把区块链结构保存在本地缓存中，实际的区块链网络最终会实现持久层的功能，把区块链数据保存至数据库中，例如BTC核心网络采用的是K-V数据库LevelDB：
BlockCache.java

public class BlockCache {


  /**
   * 当前节点的区块链结构
   */
  private List blockChain = new CopyOnWriteArrayList();
  
  public List getBlockChain() {
    return blockChain;
  }


  public void setBlockChain(List blockChain) {
    this.blockChain = blockChain;
  }
 }

第四步，有了区块链结构后，需要新增向区块链中添加区块的方法，同时每次添加区块的时候，我们需要验证新区块的有效性，例如Hash值是否正确，新区块中上一区块的Hash属性的值，与上一区块的Hash值是否相等。

另外，区块链中必须有个创世区块，我们直接通过硬编码实现:
BlockService.java

/**
 * 区块链核心服务
 * 
 * @author Jared Jia
 *
 */
@Service
public class BlockService {


  @Autowired
  BlockCache blockCache;
  
  /**
   * 创建创世区块
   * @return
   */
  public String createGenesisBlock() {
    Block genesisBlock = new Block();
    //设置创世区块高度为1
    genesisBlock.setIndex(1);
    genesisBlock.setTimestamp(System.currentTimeMillis());
    genesisBlock.setNonce(1);
    //封装业务数据
    List tsaList = new ArrayList();
    Transaction tsa = new Transaction();
    tsa.setId("1");
    tsa.setBusinessInfo("这是创世区块");
    tsaList.add(tsa);
    Transaction tsa2 = new Transaction();
    tsa2.setId("2");
    tsa2.setBusinessInfo("区块链高度为：1");
    tsaList.add(tsa2);    
    genesisBlock.setTransactions(tsaList);
    //设置创世区块的hash值
    genesisBlock.setHash(calculateHash("",tsaList,1));
    //添加到已打包保存的业务数据集合中
    blockCache.getPackedTransactions().addAll(tsaList);
    //添加到区块链中
    blockCache.getBlockChain().add(genesisBlock);
    return JSON.toJSONString(genesisBlock);
  }
  
  /**
   * 创建新区块
   * @param nonce
   * @param previousHash
   * @param hash
   * @param blockTxs
   * @return
   */
  public Block createNewBlock(int nonce, String previousHash, String hash, List blockTxs) {
    Block block = new Block();
    block.setIndex(blockCache.getBlockChain().size() + 1);
    //时间戳
    block.setTimestamp(System.currentTimeMillis());
    block.setTransactions(blockTxs);
    //工作量证明，计算正确hash值的次数
    block.setNonce(nonce);
    //上一区块的哈希
    block.setPreviousHash(previousHash);
    //当前区块的哈希
    block.setHash(hash);
    if (addBlock(block)) {
      return block;
    }
    return null;
  }


  /**
   * 添加新区块到当前节点的区块链中
   * 
   * @param newBlock
   */
  public boolean addBlock(Block newBlock) {
    //先对新区块的合法性进行校验
    if (isValidNewBlock(newBlock, blockCache.getLatestBlock())) {
      blockCache.getBlockChain().add(newBlock);
      // 新区块的业务数据需要加入到已打包的业务数据集合里去
      blockCache.getPackedTransactions().addAll(newBlock.getTransactions());
      return true;
    }
    return false;
  }
  
  /**
   * 验证新区块是否有效
   * 
   * @param newBlock
   * @param previousBlock
   * @return
   */
  public boolean isValidNewBlock(Block newBlock, Block previousBlock) {
    if (!previousBlock.getHash().equals(newBlock.getPreviousHash())) {
      System.out.println("新区块的前一个区块hash验证不通过");
      return false;
    } else {
      // 验证新区块hash值的正确性
      String hash = calculateHash(newBlock.getPreviousHash(), newBlock.getTransactions(), newBlock.getNonce());
      if (!hash.equals(newBlock.getHash())) {
        System.out.println("新区块的hash无效: " + hash + " " + newBlock.getHash());
        return false;
      }
      if (!isValidHash(newBlock.getHash())) {
        return false;
      }
    }


    return true;
  }
 }

以上关键代码实现之后，我们就构建了一个非常简单的区块链模型，包含一个基本的区块模型和一个区块链模型，并且能够生成新的区块并添加到区块链中，接下来我们进行测试。

第五步，我们编写一个Controller类进行调用：
BlockController.java

@Controller
public class BlockController {


  @Resource
  BlockService blockService;
  
  @Autowired
  BlockCache blockCache;
  
  /**
   * 查看当前节点区块链数据
   * @return
   */
  @GetMapping("/scan")
  @ResponseBody
  public String scanBlock() {
    return JSON.toJSONString(blockCache.getBlockChain());
  }
  
  /**
   * 创建创世区块
   * @return
   */
  @GetMapping("/create")
  @ResponseBody
  public String createFirstBlock() {
    blockService.createGenesisBlock();
    return JSON.toJSONString(blockCache.getBlockChain());
  }
 }

第六步，系统测试
首先系统启动后，先查看区块链中的数据，可以看到当前系统中的区块链为空：


然后我们调用创建创世区块的方法，查看返回结果：

我们把生成的创世区块添加到本地区块链中后，转换成JSON字符串返回，可以看到当前区块链中存储的有一个区块对象，至此我们已经实现了一个简单的区块链。实际的区块链系统模型要复杂的多，需要根据不同的业务场景扩展相应的字段，但是基本特征都是一样的。

（3）共识机制实现

在上章节中，我们实现了一个简单的区块链结构，并且能够生成并添加新的区块，但是问题来了，实际的区块链系统是一个多节点、分布式、去中心化的网络，每个节点通过网络交互，实时同步保存着同样的整条区块链数据，那么我们生成的区块，如何才能被其他节点认可，并同步添加到其他所有节点上呢，这个时候我们就需要一套规则，让所有网络节点的参与者达成能够达成共识，接纳并保存新的区块，也就是所谓的“共识机制”。

理论基础部分已经提到了，共识机制有很多种，各有各的优势与缺点，接下来我们就用java代码来模拟实现我们最为熟知的一种机制：工作量证明（Proof of Work），顾名思义就是对工作量的证明，在基于POW机制构建的区块链网络中，节点通过计算随机哈希散列的数值争夺记账权，求得正确的数值并生成区块的能力是节点算力的具体表现，计算的过程一般被形象地称为“挖矿”。

简单来说就是，区块链系统设定一套计算规则或者说是一套计算题，在新区块生成前，各个节点都投入到这道题的求解计算中，哪个节点先计算出结果，并得到其它节点的验证和认可，这个节点就会获得新区块的记账权，并获得系统相应的奖励，共识结束。

典型的PoW共识机制应用就是BTC网络，在BTC网络中，共识计算的目标是找到满足某个特定要求的区块Hash（哈希值）。这个区块哈希值就是工作结果的一个证明，计算工作的目的就是为了寻找到这个证明值，上一章节中，测试时我们已经见过这个Hash值：

[
    {
        "hash": "25931395e736653212f0258824df4222ae739ec2d5897310258b0857d4d3870c",
        "index": 1,
        "nonce": 1,
        "timestamp": 1580970554734,
        "transactions": [
            {
                "businessInfo": "这是创世区块",
                "id": "1"
            }
        ]
    }
]

BTC网络PoW使用的Hashcash算法，大致逻辑如下：

  1. 获取某种公开可知的数据data（BTC网络中，指的是区块头）；
  2. 添加一个计数器nonce，初始值设置为0；
  3. 计算data与nonce拼接字符串的哈希值；
  4. 检查上一步的哈希值是否满足某个条件，满足则停止计算，不满足则nonce加1，然后重复第3步和第4步，直到满足这个特定的条件为止。

接下来我们用Java代码实现这个算法，设定满足的特定条件为，Hash值前4位都是0，则计算成功（实际区块链网络中的特定条件要求更高，对计算的运算能力要求也高，并且系统随着计算难度动态调整满足的特定条件，来保证区块生成的速度）。

第一步，我们新建一个共识机制服务类，添加一个“挖矿”方法，计算成功后，获取记账权，调用添加区块的方法，把区块添加到区块链中：
PowService.java

/**
 * 共识机制
 * 采用POW即工作量证明实现共识
 * @author Administrator
 *
 */
@Service
public class PowService {


  @Autowired
  BlockCache blockCache;
  
  @Autowired
  BlockService blockService;
  
  /**
   * 通过“挖矿”进行工作量证明，实现节点间的共识
   * 
   * @return
   */
  public Block mine(){
    
    // 封装业务数据集合，记录区块产生的节点信息，临时硬编码实现
    List tsaList = new ArrayList();
    Transaction tsa1 = new Transaction();
    tsa1.setId("1");
    tsa1.setBusinessInfo("这是IP为："+CommonUtil.getLocalIp()+"，端口号为："+blockCache.getP2pport()+"的节点挖矿生成的区块");
    tsaList.add(tsa1);
    Transaction tsa2 = new Transaction();
    tsa2.setId("2");
    tsa2.setBusinessInfo("区块链高度为："+(blockCache.getLatestBlock().getIndex()+1));
    tsaList.add(tsa2);
    
    // 定义每次哈希函数的结果 
    String newBlockHash = "";
    int nonce = 0;
    long start = System.currentTimeMillis();
    System.out.println("开始挖矿");
    while (true) {
      // 计算新区块hash值
      newBlockHash = blockService.calculateHash(blockCache.getLatestBlock().getHash(), tsaList, nonce);
      // 校验hash值
      if (blockService.isValidHash(newBlockHash)) {
        System.out.println("挖矿完成，正确的hash值：" + newBlockHash);
        System.out.println("挖矿耗费时间：" + (System.currentTimeMillis() - start) + "ms");
        break;
      }
      System.out.println("第"+(nonce+1)+"次尝试计算的hash值：" + newBlockHash);
      nonce++;
    }
    // 创建新的区块
    Block block = blockService.createNewBlock(nonce, blockCache.getLatestBlock().getHash(), newBlockHash, tsaList);
    return block;
  }
  
  /**
   * 验证hash值是否满足系统条件
   * 暂定前4位是0则满足条件
   * @param hash
   * @return
   */
  public boolean isValidHash(String hash) {
    //System.out.println("难度系数："+blockCache.getDifficulty());
    return hash.startsWith("0000");
  }
}

第二步，编写测试共识机制服务的Controller类方法：
BlockController.java

/**
   * 工作量证明PoW
   * 挖矿生成新的区块 
   */
  @GetMapping("/mine")
  @ResponseBody
  public String createNewBlock() {
    powService.mine();
    return JSON.toJSONString(blockCache.getBlockChain());
  }

第三步，启动系统，进行测试。
首先执行
http://localhost:8080/create方法，生成创世区块。
其次调用
http://localhost:8080/mine方法进行工作量计算证明，生成新的区块，并添加到本地区块链中：

我们来看一下，系统后台计算的过程，此次计算共花费1048ms计算出满足条件的Hash值，共计算4850次：

至此，我们实现了一个简单的工作量证明机制，并在当前区块链系统节点上运行，完成了正确结果的计算，生成了一个新的区块。

接下来我们将会开发一个P2P网络，实现多个节点的同时运行，当一个节点挖矿完成后，通过P2P网络广播给其他节点，其他节点验证通过后，会把新产生的区块添加到自己的区块链上，进而保证整个区块链网络所有节点的数据一致性。

（4）P2P网络开发

前面我们已经实现了一个基本的区块链系统，并且实现了PoW工作量证明共识机制，通过挖矿计算出正确的结果同时生成一个新的区块添加到区块链中，但是这些都是基于单节点的运行，实际的区块链是有多个节点同时运行的分布式网络系统，所有节点同时计算抢夺记账权，共同维护一条完整的区块链。

接下来我们基于Java的WebSocket实现一个Peer-to-Peer网络，实现多个节点间的相互通信，通过本章节，我们将要实现以下功能：

  - 创建一个基于java的p2p网络
  - 运行多个节点，且多个节点通过p2p网络自动同步区块信息
  - 一个节点挖矿生成新的区块后，自动广播给其他所有节点
  - 每个节点在接收到其他节点发送的区块内容后，进行验证，验证通过添加到本地区块链上
  - 在自我节点查看整个区块链内容

开发测试本章节的功能，我们最好准备两台电脑或者虚拟机，再或者Docker集群环境也可以，便于多节点的运行测试。如果只有一台电脑也可以，各个节点运行的端口号设置为不相同即可。

第一步，开发思路整理
目前我们已经实现了单节点的区块生成，那么我们接下来只需要实现各个节点的消息同步即可。

  • 首先，通过java代码实现p2p网络的server端和client端，每个节点既是服务端也是客户端。
  • 然后，一个节点启动时，会寻找区块链网络上的有效节点，并建立socket连接（BTC网络可以通过使用“DNS”种子方式获取BTC有效节点，DNS种子提供比特币节点的IP地址列表），我们直接把节点列表配置到application.yml文件中。
  • 接着，从连接上的节点获取最新的区块信息，如果当前节点首次运行，则获取整个区块链信息，并替换到本地。
  • 之后，各个节点同时挖矿计算，哪个节点先计算完成，就把生成的新区块全网广播给其他所有节点（实际的区块链网络一直在计算，我们为了便于测试，手动触发一个节点挖矿产生区块，然后全网广播给其他所有节点）。
  • 最后，当一个节点收到广播内容后，对接收到的新区块进行验证，验证通过后添加到本地区块链上，验证的首要条件是新区块的高度必须比本地的区块链高度要高。

第二步，先实现P2P网络server端
新建一个P2PServer类，并添加一个初始化server端的方法：
P2PServer.java

/**
 * p2p服务端
 * 
 * @author Jared Jia
 *
 */
@Component
public class P2PServer {


  @Autowired
  P2PService p2pService;


  public void initP2PServer(int port) {
    WebSocketServer socketServer = new WebSocketServer(new InetSocketAddress(port)) {


      /**
       * 连接建立后触发
       */
      @Override
      public void onOpen(WebSocket webSocket, ClientHandshake clientHandshake) {
        p2pService.getSockets().add(webSocket);
      }


      /**
       * 连接关闭后触发
       */
      @Override
      public void onClose(WebSocket webSocket, int i, String s, boolean b) {
        p2pService.getSockets().remove(webSocket);
        System.out.println("connection closed to address:" + webSocket.getRemoteSocketAddress());
      }


      /**
       * 接收到客户端消息时触发
       */
      @Override
      public void onMessage(WebSocket webSocket, String msg) {
        //作为服务端，业务逻辑处理
        p2pService.handleMessage(webSocket, msg, p2pService.getSockets());
      }


      /**
       * 发生错误时触发
       */
      @Override
      public void onError(WebSocket webSocket, Exception e) {
        p2pService.getSockets().remove(webSocket);
        System.out.println("connection failed to address:" + webSocket.getRemoteSocketAddress());
      }


      @Override
      public void onStart() {


      }


    };
    socketServer.start();
    System.out.println("listening websocket p2p port on: " + port);
  }
}

第三步，实现P2P网络client端
P2PClient.java

/**
 * p2p客户端
 * 
 * @author Jared Jia
 *
 */
@Component
public class P2PClient {
  
  @Autowired
  P2PService p2pService;


  public void connectToPeer(String addr) {
    try {
      final WebSocketClient socketClient = new WebSocketClient(new URI(addr)) {
        @Override
        public void onOpen(ServerHandshake serverHandshake) {
          //客户端发送请求，查询最新区块
          p2pService.write(this, p2pService.queryLatestBlockMsg());
          p2pService.getSockets().add(this);
        }


        /**
         * 接收到消息时触发
         * @param msg
         */
        @Override
        public void onMessage(String msg) {
          p2pService.handleMessage(this, msg, p2pService.getSockets());
        }


        @Override
        public void onClose(int i, String msg, boolean b) {
          p2pService.getSockets().remove(this);
          System.out.println("connection closed");
        }


        @Override
        public void onError(Exception e) {
          p2pService.getSockets().remove(this);
          System.out.println("connection failed");
        }
      };
      socketClient.connect();
    } catch (URISyntaxException e) {
      System.out.println("p2p connect is error:" + e.getMessage());
    }
  }
}

第四步，定义P2P网络同步的消息模型
同步的消息模型，我们定义为四类，分别是：
BlockConstant.java

  // 查询最新的区块
  public final static int QUERY_LATEST_BLOCK = 1;


  // 返回最新的区块
  public final static int RESPONSE_LATEST_BLOCK = 2;


  // 查询整个区块链
  public final static int QUERY_BLOCKCHAIN = 3;


  // 返回整个区块链
  public final static int RESPONSE_BLOCKCHAIN = 4;

定义一个各个节点间传递的消息模型：
Message.java

/**
 * p2p通讯消息
 *
 * @author Jared Jia
 * 
 */
public class Message implements Serializable {
  
    private static final long serialVersionUID = 1L;
    /**
     * 消息类型
     */
    private int type;
    /**
     * 消息内容
     */
    private String data;
    
    /****set get方法省略****/
    
  }

第五步，实现向其他节点广播的方法

新建一个p2p网络服务类，向外发送消息，或者处理当前节点收到其他节点发送的请求。
P2PService.java

/**
   * 全网广播消息
   * @param message
   */
  public void broatcast(String message) {
    List socketsList = this.getSockets();
    if (CollectionUtils.isEmpty(socketsList)) {
      return;
    }
    System.out.println("======全网广播消息开始：");
    for (WebSocket socket : socketsList) {
      this.write(socket, message);
    }
    System.out.println("======全网广播消息结束");
  }

第六步，开发消息处理路由

第五步中已经实现了向外发送消息，本步骤实现接收消息。
首先设计一个服务端和客户端共用的消息路由，来分发消息给对应的处理单元。
P2PService.java

/**
   * 客户端和服务端共用的消息处理方法
   * @param webSocket
   * @param msg
   * @param sockets
   */
  public void handleMessage(WebSocket webSocket, String msg, List sockets) {
    try {
      Message message = JSON.parseObject(msg, Message.class);
      System.out.println("接收到IP地址为：" +webSocket.getRemoteSocketAddress().getAddress().toString()
          +"，端口号为："+ webSocket.getRemoteSocketAddress().getPort() + "的p2p消息："
              + JSON.toJSONString(message));
      switch (message.getType()) {
      //客户端请求查询最新的区块:1
      case BlockConstant.QUERY_LATEST_BLOCK:
        write(webSocket, responseLatestBlockMsg());//服务端调用方法返回最新区块:2
        break;
      //接收到服务端返回的最新区块:2
      case BlockConstant.RESPONSE_LATEST_BLOCK:
        handleBlockResponse(message.getData(), sockets);
        break;
      //客户端请求查询整个区块链:3
      case BlockConstant.QUERY_BLOCKCHAIN:
        write(webSocket, responseBlockChainMsg());//服务端调用方法返回最新区块:4
        break;
      //直接接收到其他节点发送的整条区块链信息:4
      case BlockConstant.RESPONSE_BLOCKCHAIN:
        handleBlockChainResponse(message.getData(), sockets);
        break;
      }
    } catch (Exception e) {
      System.out.println("处理IP地址为：" +webSocket.getRemoteSocketAddress().getAddress().toString()
        +"，端口号为："+ webSocket.getRemoteSocketAddress().getPort() + "的p2p消息错误:" 
        + e.getMessage());
    }
  }

第七步，开发消息处理单元

有了消息路由之后，接着编写不同的处理单元，处理其他节点发送来的区块或者区块链信息，总体原则是：先校验其他节点发送来的区块或者区块链的有效性，然后判断它们的高度比当前节点的区块链高度要高，如果高则替换本地的区块链，或者把新区块添加到本地区块链上。
P2PService.java

/**
   * 处理其它节点发送过来的区块信息
   * @param blockData
   * @param sockets
   */
  public synchronized void handleBlockResponse(String blockData, List sockets) {
    //反序列化得到其它节点的最新区块信息
    Block latestBlockReceived = JSON.parseObject(blockData, Block.class);
    //当前节点的最新区块
    Block latestBlock = blockCache.getLatestBlock();
    
    if (latestBlockReceived != null) {
      if(latestBlock != null) {
        //如果接收到的区块高度比本地区块高度大的多
        if(latestBlockReceived.getIndex() > latestBlock.getIndex() + 1) {
          broatcast(queryBlockChainMsg());
          System.out.println("重新查询所有节点上的整条区块链");
        }else if (latestBlockReceived.getIndex() > latestBlock.getIndex() && 
            latestBlock.getHash().equals(latestBlockReceived.getPreviousHash())) {
          if (blockService.addBlock(latestBlockReceived)) {
            broatcast(responseLatestBlockMsg());
          }
          System.out.println("将新接收到的区块加入到本地的区块链");
        }
      }else if(latestBlock == null) {
        broatcast(queryBlockChainMsg());
        System.out.println("重新查询所有节点上的整条区块链");
      }
    }
  }
  
  /**
   * 处理其它节点发送过来的区块链信息
   * @param blockData
   * @param sockets
   */
  public synchronized void handleBlockChainResponse(String blockData, List sockets) {
    //反序列化得到其它节点的整条区块链信息
    List receiveBlockchain = JSON.parseArray(blockData, Block.class);
    if(!CollectionUtils.isEmpty(receiveBlockchain) && blockService.isValidChain(receiveBlockchain)) {
      //根据区块索引先对区块进行排序
      Collections.sort(receiveBlockchain, new Comparator() {
        public int compare(Block block1, Block block2) {
          return block1.getIndex() - block2.getIndex();
        }
      });
      
      //其它节点的最新区块
      Block latestBlockReceived = receiveBlockchain.get(receiveBlockchain.size() - 1);
      //当前节点的最新区块
      Block latestBlock = blockCache.getLatestBlock();
      
      if(latestBlock == null) {
        //替换本地的区块链
        blockService.replaceChain(receiveBlockchain);
      }else {
        //其它节点区块链如果比当前节点的长，则处理当前节点的区块链
        if (latestBlockReceived.getIndex() > latestBlock.getIndex()) {
          if (latestBlock.getHash().equals(latestBlockReceived.getPreviousHash())) {
            if (blockService.addBlock(latestBlockReceived)) {
              broatcast(responseLatestBlockMsg());
            }
            System.out.println("将新接收到的区块加入到本地的区块链");
          } else {
            // 用长链替换本地的短链
            blockService.replaceChain(receiveBlockchain);
          }
        }
      }
    }
  }
3、完整系统运行与测试

第一步，打包生成测试用的可执行jar包
准备两台机器（虚拟机或者Docker集群都行），同时运行两个节点，节点信息如下：

通过mvn package -Dmaven.test.skip=true命令对工程进行打包，生成可直接运行的jar包，打包前对工程进行配置，配置信息如下图：

节点Node1打包：

节点Node2打包：

分别打包之后，生成两个节点的可执行jar包，如下：

把两个jar包分别放在对应IP的windows机器上，打开命令行模式，进入jar所在文件夹，分别执行以下命令运行两个节点：
java -jar dce-blockchain-node1.jar
java -jar dce-blockchain-node2.jar

启动节点2的时候，可以看到后台日志，已经连接上节点1，如下图所示：

第二步，对两个节点进行测试

首先，两个节点启动后，用postman分别执行
http://192.168.0.104:8080/scan和http://192.168.0.112:8090/scan请求，可以看到两个节点的区块链内容都为空。

然后，在节点1上分别执行
http://192.168.0.104:8080/create和http://192.168.0.104:8080/mine请求，来生成创世区块，以及通过挖矿产生第二个区块，执行后查看节点1的区块链信息如下：
执行
http://192.168.0.104:8080/scan结果：

[
    {
        "hash": "5303d2990c139992bdb5a22aa1dac4f2719755304e45bac03ca4a1f1688c909e",
        "index": 1,
        "nonce": 1,
        "timestamp": 1581064647736,
        "transactions": [
            {
                "businessInfo": "这是创世区块",
                "id": "1"
            },
            {
                "businessInfo": "区块链高度为：1",
                "id": "2"
            }
        ]
    },
    {
        "hash": "0000de5eea0c20c2e7d06220bc023886e88dd8784eaa2fd2d1d6c5e581061d85",
        "index": 2,
        "nonce": 4850,
        "previousHash": "5303d2990c139992bdb5a22aa1dac4f2719755304e45bac03ca4a1f1688c909e",
        "timestamp": 1581064655139,
        "transactions": [
            {
                "businessInfo": "这是IP为：192.168.0.104，端口号为：7001的节点挖矿生成的区块",
                "id": "1"
            },
            {
                "businessInfo": "区块链高度为：2",
                "id": "2"
            }
        ]
    }
]

最后，我们来验证节点2是否已经完成了节点1生成的区块链信息的网络同步，Postman执行
http://192.168.0.112:8090/scan请求，查看返回结果：

从结果可以看到，区块链网络节点2已经接收到节点1发送的区块链信息，系统日志如下：

反过来，我们在节点2上再执行一次挖矿 *** 作，可以看到节点1上，已经接收到节点2挖矿新产生的区块信息，并添加到节点1的区块链上：

至此，我们已经实现了一个完整的小型区块链网络，并实现各个节点间的通信，多个节点共同维护同一个区块链信息。

结语：
区块链系统非常庞大，涉及方方面面的技术，本人所演示的代码主要对区块链基础的一些概念进行了诠释，感兴趣的同学，还可以在此基础上继续开发，来实现例如持久层、消息的加密解密、系统账户模型、预言机、侧链技术以及智能合约等区块链系统功能。

写给每个区块链技术人员：
目前市面上流行的企业级区块链框架，例如超级账本Fabric都是国外人员在主导，而我们国内除了几家大厂外，其他很多区块链公司基本都是把人家的东西拿过来进行二次封装，然后对外声称自己公司已经掌握了区块链核心技术，并对企业提供服务，这是一种不好的现象。大家可以想想我们现在用的开发语言、框架有几个真正是国产的，我们再联想一下前段时间中兴、华为被人家核心技术卡脖子事件，就知道我们要做的事情有很多，我们需要去除浮躁，静下心来好好研究底层核心技术，这样才能实现真正的“弯道超车”！

链表高频面试题（包括反转、合并、相交、分割、环长等）
1.1 题目描述

反转一个单链表。

示例:

  • 输入: 1->2->3->4->5->NULL
  • 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

1.2 算法实现 1.2.1 算法思路

双指针：一个指针pre指向原链表当前节点的前一个节点，另一个指针next暂存当前节点的下一个节点。

依次遍历链表的各个节点，每遍历一个节点即将其指向前一个节点（倒置），主要分4步：

  1. 先备份后一个节点（以防移动指针的时候找不到下一个节点）：next = head.Next；
  2. 后一个节点的Next指向前一个节点：next.Next = pre；
  3. 前置节点后移一个位置到当前节点：pre = head;
  4. 后置节点后移一个位置到下一个节点：head = next，注意这一步（千万不要）容易忽略。
1.2.2 代码实现 
type LikedList struct{
    Val int
    Next *LikedList
}

// 头插法，倒置单链表
func reverseLikedList(head *LikedList)*LikedList{
    if(head == nil || head.Next == nil){
        return head
    }
 var pre, next *LikedList 
 // head是当前节点，pre是当前节点的前一个几点，next是当前节点的后一个节点
    for head != nil {  // 当前节点不为空
        next = head.Next    // 备份head.Next（指向当前节点的下一个节点），防止移动节点时找不到后置节点
  head.Next = pre     // 更新head.Next，后一个节点指向前一个（翻转）
  pre = head          // 前一个节点后移
  head = next   // 当前节点后移
 }
    return pre              // 注意：当pre指向原链表的最后一个节点时，head已经指向最后一个节点的Next即空节点，所以这里应返回pre
}
2.反转链表中的第m至第n个节点

题目来源：

https://leetcode-cn.com/problems/reverse-linked-list-ii

2.1 题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

  • 输入: 1->2->3->4->5->NULL, m = 2, n = 4
  • 输出: 1->4->3->2->5->NULL
2.2 算法实现 2.2.1 算法思路

有四个关键的位置需要记录：第m个节点及其前驱节点、第n个节点及其后继节点。

  1. 对整个链表遍历，将链表head的头指针向后移动m-1个节点，即为第m个节点，记其前驱节点为pre；
  2. 自第m个节点开始逆置changLen = n-m+1个节点，即将第m至第n个节点依次反转，并记录下来反转后的头结点reversedListHead和尾节点reversedListTail；
  3. 将反转后的尾节点reversedListTail的Next域与第n个节点的后继节点head连接，pre节点的Next域与reversedListHead连接。
2.2.2 代码实现 
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    changeLen := n - m + 1                      // 计算需要逆置的节点个数
    var pre *ListNode = nil                     // 初始化开始逆置的节点的前驱
    var result *ListNode = head                 // 最终转换后的链表的头结点，非特殊情况即为head
    move := m - 1                               // head向后移动m-1个位置指向第m个节点
    for(head != nil && move > 0){               // 将head后移m-1个位置，即
        pre = head                              // for循环后pre指向第m个节点的前驱节点
        head = head.Next                        // for循环后head指向第m个节点
        move--
    }

    var reversedListTail *ListNode = head       // 此时reversedListTail指向的是第m个节点，该节点即是链表片段反转后的尾节点
    var reversedListHead *ListNode = nil        // 记录链表片段反转后的头结点
    for(head != nil && changeLen > 0){          // 逆置changeLen个节点
        next := head.Next                       // 暂存当前节点的下一个节点
        head.Next = reversedListHead            // 当前节点的Next指针域指向新开辟的反转后的头结点
        reversedListHead = head                 // 反转后的链表的头结点后移一个位置
        head = next                             // 当前节点后移一个节点
        changeLen--                             // 每完成一个节点逆置，changLen--
    }

    reversedListTail.Next = head                // 连接逆置后的链表尾与逆置段的后一个节点，翻转后的尾节点指向第n个节点的下一个节点
    if(pre != nil){                             // 如果pre不为空，说明不是从第1个节点开始逆置的，即m > 1 
        pre.Next = reversedListHead             // 将逆置链表开始的节点前驱与逆置后的头结点连接起来
    }else{                                      // 如果pre为空，说明m=1，即从第1个节点开始逆置，结果即为逆置后的头结点
        result = reversedListHead
    }
    return result
}
3.求两个链表之间的交点 3.1 题目描述

题目来源：

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

  • 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
  • 输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

推荐：250期面试题汇总

示例 2：

  • 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
  • 输出：Reference of the node with value = 2

输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

  • 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
  • 输出：null

输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
3.2 算法实现 3.2.1 算法思路
  1. 对两个链表ListNode1和ListNode2分别遍历，计算出其长度len1和len2；
  2. 长链表的头指针后移abs(len1 - len2)个节点；
  3. 当链表未遍历到头，两链表指向同一个节点时，该节点即为两链表的交点，没有指向同一个节点则两个头结点指针继续后移；遍历完还没有找到，则说明没有交点，返回nil。
3.2.2 代码实现 
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var lenA, lenB int                                      // 分别记录链表headA和链表headB的长度    
    lenA = getListLength(headA)
    lenB = getListLength(headB)

    if lenA > lenB {
        headA = forwardDeltaLenNode(lenA, lenB, headA)      // headA链表的头结点指向移动多出的节点个位置后
    }else{
        headB = forwardDeltaLenNode(lenB, lenA, headB)      // 如果链表headB长，移动其头结点到相应位置
    }
    for headA != nil && headB != nil {      // 没有到达链表末尾
        if(headA == headB){                 // 当前两个链表的节点相同，即指向同一个节点，说明找到的交点；否则，两链表同时后移
            return headA
        }
        headA = headA.Next                  
        headB = headB.Next
    }
    return nil                              // 遍历到链表末尾还没有找到同一个节点，说明两链表没有交点
}

// 逐个节点遍历，获取链表长度
func getListLength(head *ListNode)int{
    var lengthList int 
    for head != nil {
        lengthList++
        head = head.Next
    }
    return lengthList
}

// 较长链表移动 长链表长度-短链表长度 个节点后对应的头指针
// 参数longLen和shortLen分别表示长链表和短链表的长度，longList对应长链表
func forwardDeltaLenNode(longLen, shortLen int, longList *ListNode)*ListNode{
    deltaLen := longLen - shortLen
    for longList != nil && deltaLen != 0{
        longList = longList.Next
        deltaLen--
    }
    return longList             // 如果longList为nil或者deltaLen=0直接返回此时的头结点longList
}
4.判断链表是否有环；如果有环，给出环所在的起始节点及环的长度。 4.1 判断链表是否有环 4.2 给出有环链表的环的起始节点及长度 5.将链表换分为以某个值x为界限的前后两部分

链表划分依据：链表前面的部门小于x，后面部分大于等于x，且原有节点的相对顺序不变。如：将1->3-7->2->5->3->6-9-2划分为以5为界限的前后两部分：1->3->2->3->2 ->7->5->6->9

5.1 问题描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

  • 输入: head = 1->4->3->2->5->2, x = 3
  • 输出: 1->2->2->4->3->5

链接：

https://leetcode-cn.com/problems/partition-list

5.2 算法实现 5.2.1 算法思路

链表分为前后两个部分，可以先依次遍历链表，将小于x的节点依次插入到preHead指向的前半部分链表后面，将大于等于x的节点连接到postHead对应的另一个链表中；链表遍历完将preHead的尾节点的Next域指向postHead结点的下一个节点，postHead的尾节点的Next域置为空，即实现了前后两个链表的连接。

为了连接preHead和postHead两个链表，需要分别知道两个链表的尾部，这里使用prePtr和postPtr指针分别对preHead和postHead进行遍历，知道两个链表的尾节点。

  • 前一个链表：preHead->1->2->2
  • 后一个链表：postHead->4->3->5
5.2.2 代码实现 
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    //var preHead, postHead *ListNode     // 前后两部分链表的头结点，不能这么声明，这样声明的话两者都为&ListNode{0, nil}其中Next域为nil，当运行到prePtr.Next = head时会报panic: runtime error:invalid memory address or nil pointer deference错误
    preHead := &ListNode{0, nil}        // 生成一个preHead链表的头结点，该节点固定一直不对其移动，改头节点的Val为多少都不影响结果，因为使用的是头结点的Next节点
    postHead := &ListNode{0, nil}       // 生成一个postHead链表的头结点，该节点固定不动
    prePtr := preHead                   // prePtr指针对preHead链表进行遍历，注意：开始时其指向preHead
    postPtr := postHead
    for head != nil {                   // 遍历原链表
        if(head.Val < x ){              // 小于x的节点尾插到preHead链表后面
            prePtr.Next = head          // prePtr的Next域指向当前节点，即将当前节点从preHead链表尾部prePtr依次插入
            prePtr = head               // prePtr指针后移一位，指向当前节点
        }else{                          // 大于等于x的节点放在postHead链表的后面
            postPtr.Next = head         // 将当前节点插入到postHead链表尾节点postPtr后面
            postPtr = head              // postHead链表的尾节点后移一位
        }
        head = head.Next                // 当前指针后移一位
    }
    // 对head链表遍历结束分为preHead和postHead两个子链表
    prePtr.Next = postHead.Next         // 注意：这里是将preHead链表的尾节点prePtr的Next域指向postHead链表头结点的下一个节点
    postPtr.Next = nil                  // postPtr的尾节点的Next域指向空
    return preHead.Next                 // 返回preHead链表的Next之后的链表

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/735916.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表（0条）

保存