当前位置: 首页 > 编程笔记 >

Java双向链表倒置功能实现过程解析

高山
2023-03-14
本文向大家介绍Java双向链表倒置功能实现过程解析,包括了Java双向链表倒置功能实现过程解析的使用技巧和注意事项,需要的朋友参考一下

题目要求:Java实现一个双向链表的倒置功能(1->2->3 变成 3->2->1)

提交:代码、测试用例,希望可以写成一个Java小项目,可以看到单元测试部分

该题目的代码,已经放到了我的github上,地址为:https://github.com/jiashubing/alibaba-linkedlist-reversed.git

最关键的是自定义节点Node 和自定义双向链表MyLinkedList 两个类,倒置的方法放在自定义链表类里reversed() ,具体的说明都在代码中

自定义节点类Node.java,有三个参数 :T data(当前值)、Node<T> left(左节点)、Node<T> right(右节点)

定义双向链表类MyLinkedList.java,有两个参数:Node<T> head(头结点)、Node<T> current(当前节点,也是最后一个节点)

  添加节点的方法void add(T data):添加的第一个节点Node,它的左节点为null,最后一个节点的右节点也为null,中间的每个节点的左右节点都有值

  倒置链表的方法reversed():把每个节点的左右节点交换,并且把链表的首尾节点也交换,就可以了。这里需要考虑的是循环的终止条件。我的实现如下:

public void reversed() {
  if (head == null || head.getRight() == null) {
    return;
  }
  current = head;
  while(true) {
    //交换左右节点
    Node<T> tmp = head.getLeft();
    head.setLeft(head.getRight());
    head.setRight(tmp);

    //如果左节点为空,则终止,否则循环执行
    if (head.getLeft() == null) {
      return;
    } else {
      head = head.getLeft();
    }
  }
}

剩下的测试用例,就简单了。下面是我的github上的代码,记录下:

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
     xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
  <modelVersion>4.0.0</modelVersion>

  <groupId>cn.jiashubing</groupId>
  <artifactId>alitest</artifactId>
  <version>1.0-SNAPSHOT</version>

  <dependencies>
    <dependency>
      <groupId>junit</groupId>
      <artifactId>junit</artifactId>
      <version>4.12</version>
    </dependency>
  </dependencies>

</project>

Node.java

package cn.jiashubing;

/**
 * 自定义节点
 *
 * @author jiashubing
 * @since 2018/3/30
 */
class Node<T> {

  /**
   * 当前值
   */
  private T data;

  /**
   * 左节点
   */
  private Node<T> left;

  /**
   * 右节点
   */
  private Node<T> right;

  Node(T data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  T getData() {
    return data;
  }

  void setData(T data) {
    this.data = data;
  }

  Node<T> getLeft() {
    return left;
  }

  void setLeft(Node<T> left) {
    this.left = left;
  }

  Node<T> getRight() {
    return right;
  }

  void setRight(Node<T> right) {
    this.right = right;
  }
}

MyLinkedList.java

package cn.jiashubing;

/**
 * 自定义双向链表
 *
 * @author jiashubing
 * @since 2018/3/30
 */
public class MyLinkedList<T> {
  /**
   * 头结点
   */
  private Node<T> head;

  /**
   * 当前节点
   */
  private Node<T> current;

  /**
   * 添加节点
   * 如果头节点为空,则赋值为当前节点
   * 否则,要双向设置,当前节点向后移动一位
   *
   * @param data 当前节点的值
   */
  public void add(T data) {
    if (head == null) {
      head = new Node<T>(data);
      current = head;
    } else {
      Node<T> tmp = new Node<T>(data);
      current.setRight(tmp);
      tmp.setLeft(current);
      current = current.getRight();
    }
  }

  /**
   * 正向打印链表
   *
   * @param node 当前节点
   */
  public void print(Node<T> node) {
    if (node == null) {
      return;
    }

    Node<T> tmp = node;
    while (tmp != null) {
      System.out.print(tmp.getData() + " ");
      tmp = tmp.getRight();
    }
    System.out.println("");
  }


  /**
   * 反向打印链表
   *
   * @param node 当前节点
   */
  public void printRev(Node<T> node) {
    if (node == null) {
      return;
    }

    Node<T> tmp = node;
    while (tmp != null) {
      System.out.print(tmp.getData() + " ");
      tmp = tmp.getLeft();
    }
    System.out.println("");
  }


  /**
   * 链表倒置
   */
  public void reversed() {
    if (head == null || head.getRight() == null) {
      return;
    }
    current = head;
    while(true) {
      //交换左右节点
      Node<T> tmp = head.getLeft();
      head.setLeft(head.getRight());
      head.setRight(tmp);

      //如果左节点为空,则终止,否则循环执行
      if (head.getLeft() == null) {
        return;
      } else {
        head = head.getLeft();
      }
    }
  }

  public Node<T> getHead() {
    return head;
  }

  public Node<T> getCurrent() {
    return current;
  }

}

JunitTest.java

import cn.jiashubing.MyLinkedList;
import org.junit.Before;
import org.junit.Test;

/**
 * @author jiashubing
 * @since 2018/3/30
 */
public class JunitTest {

  private MyLinkedList<Integer> list;

  @Before
  public void setNum() {
    list = new MyLinkedList<Integer>();
    for (int i = 1; i < 4; i++) {
      list.add(i);
    }
    System.out.println("正向打印: ");
    list.print(list.getHead());
  }

  @Test
  public void test1() {
    System.out.println("链表倒置后正向打印 ");
    list.reversed();
    list.print(list.getHead());
  }

  @Test
  public void test2() {
    System.out.println("逆向打印 ");
    list.printRev(list.getCurrent());
  }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持小牛知识库。

 类似资料:
  • 本文向大家介绍小程序实现列表倒计时功能,包括了小程序实现列表倒计时功能的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了小程序实现列表倒计时的具体代码,供大家参考,具体内容如下 效果 HTML代码 CSS代码 JS代码(得到后台数据查询用FIND方法插入字段,直接遍历会有问题) 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。

  • 本文向大家介绍Android 实现列表倒计时功能,包括了Android 实现列表倒计时功能的使用技巧和注意事项,需要的朋友参考一下 单个计时器,然后遍历数据 刷新条目; 两种实现方式:1、Handler轮询; 2、子线程睡眠(时间到后 移除列表中的条目会有问题); 代码很简单,没有任何难度,列表使用 RecyclerView+BaseRecyclerViewAdapterHelper实现;  Ge

  • 本文向大家介绍双向链表和双向循环链表?相关面试题,主要包含被问及双向链表和双向循环链表?时的应答技巧和注意事项,需要的朋友参考一下 双向链表: 包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。 双向循环链表: 最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

  • 主要内容:双向链表的创建目前我们所学到的 链表,无论是动态链表还是 静态链表,表中各节点中都只包含一个指针(游标),且都统一指向直接后继节点,通常称这类链表为 单向链表(或 单链表)。 虽然使用单链表能 100% 解决逻辑关系为 "一对一" 数据的存储问题,但在解决某些特殊问题时,单链表并不是效率最优的存储结构。比如说,如果算法中需要大量地找某指定结点的前趋结点,使用单链表无疑是灾难性的,因为单链表更适合 "从前往后"

  • 双向链表 结构体 struct   rt_list_node   双向链表节点 更多...   宏定义 #define  rt_container_of(ptr, type, member)   ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))   获取type结构体中member成员在这个结构体中的偏移   #de

  • 双向链表 Linux 内核自己实现了双向链表,可以在 include/linux/list.h 找到定义。我们将会从双向链表数据结构开始内核的数据结构。为什么?因为它在内核里使用的很广泛,你只需要在 free-electrons.com 检索一下就知道了。 首先让我们看一下在 include/linux/types.h 里的主结构体: struct list_head { struct l