面经--逆转链表

如何逆转链表呢？本篇介绍两种常见方法：

1. 遍历
2. 递归

遍历

private static Node reverseHead(@Nonnull Node 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;
}

递归

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;  
}