单链表翻转

单链表翻转也是面试中经常会被问到的一个经典算法。解决这个问题，最常想到的是递归，或者借助外部数组村组来实现。但是这两种方式的复杂度都偏高。

本文主要介绍使用指针来实现复杂度为O(1)的单链表翻转方法。

定义链表节点

首先定义链表节点

class Node {
    private int val;
    private Node next;

    public Node(int val) {
        this.val = val;
        this.next = null;
    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public String print() {
        StringBuilder sb = new StringBuilder();
        if (next == null) {
            sb.append(val);
        } else {
            sb.append(val);
            sb.append("->");
            sb.append(next.print());
        }
        return sb.toString();
    }
}

递归法

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

public Node recursion(Node head) {
    if (head == null || head.getNext() == null) {
        return head;
    }
    Node next = head.getNext();
    Node reHead = recursion(next);// 先翻转后续节点
    next.setNext(head);// 将当前节点的指针域指向前一个节点
    head.setNext(null);// 将前一个节点的指针域置空
    return reHead; // 翻转后新链表的节点
}

三指针法

递归反转法是从后往前逆序反转指针域的指向，而三指针法是从前往后反转各个结点的指针域的指向。
基本思路是：将当前节点cur的下一个节点 cur.getNext()缓存到temp后，然后更改当前节点指针指向上一结点pre。也就是说在反转当前结点指针指向前，先把当前结点的指针域用tmp临时保存，以便下一次使用。

public Node nonRecursion(Node head) {
       if (head == null || head.getNext() == null) {
           return head;
       }

       Node pre = head;
       Node cur = pre.getNext();
       Node next;
       while (cur != null) {
           next = cur.getNext();

           cur.setNext(pre);
           
           pre = cur;
           cur = next;
       }
       // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
       head.setNext(null);
       return pre;
   }