5.1.13 13.反转链表

一、题目

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

二、解题思路

①遍历。将指向下一个节点的指针指向上一个节点。

②递归。先让指向下一个节点的指针为空，然后递归调用，最后再将指向下一个节点的指针指向上一个节点。

三、解题代码

遍历

    /**
     * 反转单链表
     * @param head
     * @return
     */
    private static Node reverseHead(Node head) {
        if (head == null) {
            return head;
        }

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

            pre = cur;
            cur = next;
        }
        head.nextNode = null;
        head = pre;
        return head;
    }

递归

    /**
     * 递归反转
     * @param head
     * @return
     */
    private static Node reverseByRecur(Node current) {
        if (current == null || current.nextNode == null) return current;  
         Node nextNode = current.nextNode;  
         current.nextNode = null;  
         Node reverseRest = reverseByRecur(nextNode);  
         nextNode.nextNode = current;  
         return reverseRest;  
    }