一、题目

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

二、解题思路

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

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

三、解题代码

遍历

  1.     /**
  2.      * 反转单链表
  3.      * @param head
  4.      * @return
  5.      */
  6.     private static Node reverseHead(Node head) {
  7.         if (head == null) {
  8.             return head;
  9.         }
  11.         Node pre = head;
  12.         Node cur = head.nextNode;
  13.         Node next = null;
  14.         while(cur != null){
  15.             next = cur.nextNode;
  16.             cur.nextNode = pre;
  18.             pre = cur;
  19.             cur = next;
  20.         }
  21.         head.nextNode = null;
  22.         head = pre;
  23.         return head;
  24.     }

递归

  1.     /**
  2.      * 递归反转
  3.      * @param head
  4.      * @return
  5.      */
  6.     private static Node reverseByRecur(Node current) {
  7.         if (current == null || current.nextNode == null) return current;  
  8.          Node nextNode = current.nextNode;  
  9.          current.nextNode = null;  
  10.          Node reverseRest = reverseByRecur(nextNode);  
  11.          nextNode.nextNode = current;  
  12.          return reverseRest;  
  13.     }