189 8069 5689

Java​逆转单向链表怎么实现-创新互联

这篇文章主要讲解了“Java逆转单向链表怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java逆转单向链表怎么实现”吧！

创新互联是一家专注于成都网站设计、网站建设、外贸网站建设与策划设计,庐山网站建设哪家好?创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:庐山等地区。庐山做网站价格咨询:18980820575

首先这是一个单向的链表，不同于 Java 里面的 LinkedList，它是双向的链表。链表中每个节点之间通过 next 指针串接起来，会有一个链表头和链表尾指针 hold 住整个链表。逆转的任务就是将 head -> a -> b -> c -> d <- tail 变成 head -> d -> c -> b -> a <- tail。

链表结构表示



class Node {
    T value;
    Node next;

    Node(T value) {
        this.value = value;
    }
}

class ReverseLinkedList {
  Node head, tail;
}

链表构造器

我们需要将所有的元素一个一个的使用 next 指针串接起来，链表的头尾节点要用 head 和 tail 变量把持住。加入新元素时，需要调整尾部节点的 next 指针，指向新加入的元素节点。

class ReverseLinkedList {
  private Node head, tail;

  public ReverseLinkedList(T... values) {
    for (T value : values) {
        if (tail == null) {
            // 第一个节点
            head = tail = new Node<>(value);
        } else {
            // 后面的节点往链表尾部追加
            Node oldTail = tail;
            oldTail.next = tail = new Node<>(value);
        }
    }
  }
}

ReverseLinkedList l = new ReverseLinkedList<>(1,2,3,4,5,6);

链表内容呈现

我们需要提供一个链表的输出方法，以便快速对比逆转后链表的内容是否正确


class ReverseLinkedList {
  private Node head, tail;

  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    Node cur = head;
    while (cur != null) {
        sb.append(cur.value);
        cur = cur.next;
        if (cur != null) {
            sb.append(',');
        }
    }
    sb.append(']');
    return sb.toString();
  }
}

迭代逆转算法

循环调整 next 指针是最容易想到的方法，但是要将指针精确地逆转正确其实并不容易。下面代码中的循环部分很短，但是却很精致，使用了三个临时局部变量 cur、next 和 nextnext，稍有不慎就会出错。

当我写完下面这段代码时，虽然可以正常运行出期望的结果，但是总当心哪里会有遗漏，是不是什么地方少了个 if else，这就是编写算法代码时常见的心理状态。

class ReverseLinkedList {
  private Node head, tail

  public ReverseLinkedList reverseByLoop() {
    // 空链表或者单元素都无需处理
    if (head == tail) {
        return this;
    }
    Node cur = head;
    Node next = cur.next;
    while (next != null) {
        Node nextnext = next.next;
        next.next = cur;
        cur = next;
        next = nextnext;
    }
    tail = head;
    tail.next = null;
    head = cur;
    return this;
  }
}

递归逆转算法

使用递归的思想来解决这个问题也是一个很好的主意，只不过当链表特别长时，调用栈会很深，链表长到一定程度就会抛出臭名昭著的异常 StackOverflowException。

class ReverseLinkedList {
  private Node head, tail

  public ReverseLinkedList reverseByRecursive() {
    Node oldTail = tail;
    tail = reverseFrom(head);
    tail.next = null;
    head = oldTail;
    return this;
  }

  private Node reverseFrom(Node from) {
      if (from == tail) {
      return from;
    }
    Node end = reverseFrom(from.next);
    end.next = from;
    return from;
  }
}

感谢各位的阅读，以上就是“Java逆转单向链表怎么实现”的内容了，经过本文的学习后，相信大家对Java逆转单向链表怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！


标题名称：Java​逆转单向链表怎么实现-创新互联
网站网址：http://jkwzsj.com/article/jjipo.html

其他资讯