Java链表实现以及链表倒置

链表一种在物理存储单元上非连续、非顺序的一种存储结构，元素通过链表中的指针链接次序实现。链表是由节点组成，每一个节点包括两部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。相比于线性表，操作变得复杂，但是对于数据的删除和增加要快。

链表结构图.png

Java代码实现链表

public class MyList {

    private Node head; // 定义一个头节点
    private Node current; // 记录当前节点

    public static void main(String[] args) {
        MyList myList = new MyList();
        for (int i = 0; i < 5; i++) {
            myList.addData(i); // 循环添加5个元素
        }

        myList.printList(myList.head);   //打印链表
    }

    // 往链表中添加数据
    private void addData(int data) {
        if (head == null) {
            head = new Node(data); // 如果头节点为空，就新建一个头结点
            current = head; // 记录当前节点为头结点
        } else {
            current.next = new Node(data); // 新建一个节点，当前节点的指针域指向它
            current = current.next; // 当前节点位置后移
        }
    }

    // 打印链表
    private void printList(Node head) {
        if (head != null) { // 确定链表不为空
            current = head;
            while (current!= null) { // 最后一个节点的为空
                System.out.print(current.data + "-->");
                current = current.next; // 当前节点往后移动一个位置
            }
        }
    }

    // 自定义节点类，包含数据域和指针域
    class Node {
        int data; // 数据域
        Node next; // 指针域

        public Node(int data) {
            this.data = data;
        }
    }
}

链表倒置问题
一些公司经常拿来做为笔试题，至少在我刚出来实习时前几次面试中就碰到过两次。所以还是有必要进行细心准备一下。以下在上面实现的链表基础上进行倒置。

• 递归倒置法

在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始，逆向反转各个结点的指针域指向

    // 递归倒置链表
    private Node resetList1(Node head) {
        if (head == null || head.next == null) {   
            return head;                        // 若为空链或者当前结点在尾结点，则直接返回
        } else {
            Node newHead = resetList1(head.next);   //反转后续节点head.next
            head.next.next = head;              //将当前节点的指针域向前移
            head.next = null;                   //前一节点的指针域置空
            return newHead;
        }
    }

• 遍历反转法

从前往后，通过生成一个临时节点next进行下一节点缓存，指针反转后，再将缓存节点赋值给当前节点，这样往后移动

    // 遍历方法倒置
    private Node resetList2(Node head) {
        Node current = head;
        Node next = null;
        Node newHead = null;
        if (head == null || head.next == null) {
            return head;
        } else {
            while (current != null) {    //为空时到了尾节点
                next = current.next;     //新结点next缓存下一个节点
                current.next = newHead;  //指针域反转
                newHead = current;       //将当前节点给newHead
                current = next;          //移动到下一个节点
            }
        }
        return newHead;
    }