题目

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

示例

• 示例1

• 输入: 1->2->3->4->5->NULL
• 输出: 5->4->3->2->1->NULL

代码

• 递归

// Java
ListNode newHead = null;
public ListNode reverseList(ListNode head) {
    // 截止条件
    if(head == null || head.next == null) return head;
    // 递归调用
    newHead = reverseList(head.next);
    // 处理指向
    head.next.next = head;
    head.next = null;

    return newHead;
}

// C++
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL)    return NULL;
        if(head->next == NULL)    return head;
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return node;
    }
};

代码分析：图解 from LeetCode 用户 郁郁雨

• 迭代

// 迭代
public ListNode reverseList_2(ListNode head) {
    // 如果想遍历的时候更改指向，得定义3个结点指针
    // 2 个用来更改指向，一个用来保存下一个结点
    ListNode preNode = null;
    ListNode cur = head;
    while(cur != null){
        // 获取下一个结点
        ListNode next = cur.next;
        // 更改指向
        cur.next = preNode;
        preNode = cur;
        cur = next;
    }
    return preNode;
}

题目：fan-zhuan-lian-biao-lcof