题目描述

反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

  • 迭代方法–使用头插法重新构建单链表
    1. 新建一个指针ret作为新链表的起始结点，初始值为nullptr(默认肯定是null)；
    2. 摘下链表head的首结点作为待插入结点，若head为空则停止并返回ret；
    3. 使用头插法将摘下的结点插入到新链表中；
    4. 重复2,3步骤。
  • 递归方法

AC代码

反转链表.cpp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverseList_Recusive(head);
    }
    ListNode* reverseList_Recusive(ListNode* head) {
        return reverseList_Recusive(nullptr, head);
    }

    ListNode* reverseList_Recusive(ListNode* pre, ListNode* cur) {
        if(nullptr == cur)
            return pre;
        ListNode* next = cur->next;
        cur->next = pre;
        return reverseList_Recusive(cur, next);
    }

    ListNode* reverseList_Iterative_HeadInsert(ListNode* head) {
        ListNode* ret = nullptr;
        while(nullptr != head)
        {
            ListNode* next = head->next;
            head->next = ret;
            ret = head;
            head = next;
        }
        return ret;
    }
};