(链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

❓剑指 Offer 24. 反转链表

难度：简单

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

示例:

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

限制：

0 <= 节点个数 <= 5000

注意：本题与 206. 反转链表相同。

💡思路：

法一：递归

可以将本问题分解成子问题：

1->(剩余部分的反转)，而1 始终指向 2，即1->2
所以第一层递归的结果以为： 5->4->3->2 <-1
每一层以此类推。

法二：迭代

头插法。

🍁代码：(C++、Java)

法一：递归
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* temp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return temp;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

法二：迭代
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* h0 = new ListNode(-1);
        ListNode* temp = head;
        while(head != nullptr){
            head = head->next;
            temp->next = h0->next;
            h0->next = temp;
            temp = head;
        }
        head = h0->next;
        delete(h0);
        return head;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode h0 = new ListNode(-1);
        ListNode temp = head;
        while(head != null){
            head = head.next;
            temp.next = h0.next;
            h0.next = temp;
            temp = head;
        }
        head = h0.next;
        return head;
    }
}