单向链表反转

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

遍历

public class Node {
    public int value;
    public Node nextNode;
}

public Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node pre = head;
    Node cur = head.next;
    Node next = null;
    while (cur != null) {
        // 1. 当前节点的前置节点赋值给当前节点的后置节点
        cur.nextNode = pre;
        // 2. cur、pre、next分别向后移动一位, next起到占位的作用;
        next = cur.nextNode;
        pre = cur;
        // 3. 占位节点next每次循环结束以后, 赋值给cur用于下一次循环的起始节点
        cur = next;
    }
    // 遍历结束, 释放head的引用
    head.nextNode = null;
    head = pre;
}

递归

public class Node {
    public int value;
    public Node nextNode;
}

public Node reverse(Node curNode) {
    // 1.递归的出口
    if (curNode == null || curNode.nextNode == null) {
        return curNode;
    }
    // 2. 当前curNode不是尾节点, 也不是倒数第二个节点
    Node nextNode = curNode.nextNode;
    // 3. 节点反转, 需要将当前节点的后置节点置为null
    curNode.nextNode = null;
    // 4. 递归调用, 此时应该返回nextNode的后置节点
    Node reverseNode = reverse(nextNode);
    nextNode.nextNode = curNode;
    return reverseNode;
}