关于java:leetcode-206-反转链表简单

链表

概念:

• 区别于数组，链表中的元素不是存储在内存中间断的一片区域，链表中的数据存储在每一个称之为「结点」复合区域里，在每一个结点除了存储数据以外，还保留了到下一个结点的指针（Pointer）。

• 因为不用按顺序存储，链表在插入数据的时候能够达到 O(1)O(1) 的复杂度，然而查找一个结点或者拜访特定编号的结点则须要 O(n) 的工夫。

利用

• HashMap Node 节点，Node节点有本身的值和 next 指向：

  //HashMap Node 局部源码static class Node<K,V> implements Map.Entry<K,V> {  final int hash;  final K key;  V value;  Node<K,V> next;  Node(int hash, K key, V value, Node<K,V> next) {      this.hash = hash;      this.key = key;      this.value = value;      this.next = next;  }}

• LinkedList Node 结点应用双链表

//LinkedList 局部源码private static class Node<E> {    E item;    Node<E> next;    Node<E> prev;    Node(Node<E> prev, E element, Node<E> next) {        this.item = element;        this.next = next;        this.prev = prev;    }}

题目形容

解题思路

单链表的反转就是把链表的指向换一个方向，由从左往右变成从右变左。

次要解题思路是拆分每一个指针。

上图从 1 指向 2 变成 2 指向1，也就是须要设置 2 节点的next = 1，在做指向的扭转之前要先将 2 节点的 next 存起来，而后扭转 2 节点的next：

• 创立一个空链表 node，用来存储反转的链表。
• 存储链表的 next。
• 链表的 next 指向 node。
• 以后链表赋值给 node。
• 循环遍历下一个节点

Java 解题代码：

class Solution {    public ListNode reverseList(ListNode head) {        ListNode cur = head;        // 创立一个空链表        ListNode node= null;        while(cur != null) {            // 存储 next            ListNode next = cur.next;            // 以后链表指向指向新的链表            cur.next = node;            // 以后节点赋值给 node            node = cur;            // 遍历下一个节点            cur = next;         }        return pre;    }}

如果感觉文章对你有帮忙的话，请点个赞吧!