单链表及其反转

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点由元素和指针构成，元素是存储数据的存储单元，指针是连接每个结点的地址数据，本文将介绍什么是单链表以及单链表的翻转，主要内容如下：

什么是单链表
遍历反转单链表
递归反转单链表

什么是单链表#

对于单链表的每个结点，都有两块存储区域，一块存储对应节点的数据，另一块存储该节点的下一个结点的地址，可以称之为后继指针 (next)，单链表图示如下：

头结点：链表的第一个结点，用来记录链表的基地址
尾结点：链表的最后一个结点，其后继指针（next）指向空地址

遍历反转单链表#

记住一点，链表反转实际上就是将链表中的指针指向相反方向，假设单链表为 A->B->C->D，反转后则为 D->C->B->A，通过遍历方式反转单链表就是将每个结点依次反转。

依次反转时，A 结点的 next 指针指向 null, 然后 B 结点的 next 的指针指向 A 结点，最终遍历完成单链表的反转，遍历反转单链表图示如下：

具体代码如下：

/**
 * 链表反转（遍历）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思路：对于链表A->B->C->D将其反转就是将头结点也就是A结点指向null,在将B结点指向A结点，依稀类推
     *      反转过程中要注意链表的断开，防止丢失断开的链表
     *
     * 链表反转实际上就是将链表中的指针指向相反方向
     */

    Node<T> tempNode = null;
    while (head != null) {
        // 记录因为反转断开的链表
        Node<T> nextNode = head.next;
        // 链表反转
        head.next = tempNode;
        // 移动tempNode指针
        tempNode = head;
        // 移动head指针
        head = nextNode;
    }
    return tempNode;
}

递归反转单链表#

第二种反转单链表的方式就是递归，核心思想就是大问题转小问题，通俗来讲就是多个结点的单链表都是都可以进一步划分为更小的单链表，如一个节点的单链表就是它本身，两结点点的单链表 A->B->null，反转时将相邻结点指针反向即可，即将结点 B 的 next 指针指向 A，此时 A 的 next 指针还是指向 B，所以需要将 A 的 next 指针指向 null，代码表示如下：

// 链表A->B->null反转
B.next = A;
A.next = null;

使用递归方式反转单链表图示如下：

具体代码如下：

/**
 * 链表反转（递归）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思路：使用递归思想解决
     *
     * 链表反转始终要记得两个相邻结点的指针反向
     */

    if (head == null || head.next == null) {
        return head;
    }
    
    // newNode即最终反转后的头结点
    Node<T> newNode = reverse1(head.next);
    head.next.next = head;
    head.next = null;
    return newNode;
}

如上介绍了单链表及其反转的两种方式，如有错误欢迎指正。