• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    二、解题思路

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

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

    三、解题代码

    遍历

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