链表反转

概述

链表反转是非常经典的面试题，要实现此功能，需先实现链表的数据结构。

链表类

public class Node<K,V> {
    private final K key;
    private V value;
    private Node<K, V> next;

    public Node(K key, V value, Node<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

获得单向链表方法

    /**
     * 头插法生成的单向链表--后来的在链表头部
     */
    public static Node<Integer, Integer> getOneWayLinkedList(int length) {
        Node<Integer, Integer> temp = null;
        for (int i = 1; i <= length; i++) {
            //头插法：先来的在链尾
            temp = new Node<>(i, i, temp); 
        }
        return temp;   //8 -> 1 -> null
    }

输出单向链表方法

    /**
     * @param linkedList 单向链表，从链表头的位置开始。 8 -> 1
     */
    public static void forLinkedList(Node<Integer, Integer> linkedList) {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        while (linkedList != null) {
            sb.append("[k：").append(linkedList.getKey()).append(" v：").append(linkedList.getValue()).append("]");
            linkedList = linkedList.getNext();
        }
        sb.append("}");
        System.out.println(sb.toString());
    }

逆序单链表

• First Blood 引入中间变量节点

public static Node<Integer, Integer> reverse1(Node<Integer, Integer> head) {
        //反转之后链表
        Node<Integer, Integer> reverse = null;
        //原链表
        Node<Integer, Integer> current = head;
        while (current != null) {
            Node<Integer, Integer> temp = current;
            current = current.getNext();
            temp.setNext(reverse);
            reverse = temp;
        }
        return reverse;   //1 -> 8 -> null
}

• Double kill 递归

public static Node<Integer, Integer> reverse2(Node<Integer, Integer> head) {
        //当为空或者本节点为末尾节点的时候
        if (head == null || head.getNext() == null) {
            return head;
        }
        Node<Integer, Integer> reversedHead = reverse2(head.getNext());
        //获取先前的下一个节点，让该节点指向自身     //8 -> 1 -> null
        head.getNext().setNext(head);
        //破坏以前自己指向下一个节点
        head.setNext(null);
        //层层传递给最上面的
        return reversedHead;
}