Reverse Linked List

1，题目要求

Reverse a singly linked list.

翻转一个单链表。

Reverse Linked List

2，题目思路

对于这道题，是单链表问题的一个非常经典的问题。一般来说，这个问题有两种解决办法：迭代与递归。

迭代：
迭代的方法相对来说比较简单。
我们首先定义一个节点，作为开始节点（NULL），然后在循环的过程中：

记录当前节点的下一个节点。
让当前节点指向上一个节点。
让当前节点变为下一个节点。

这样，在对该单链表遍历一遍之后，就可以将这个链表翻转了。

递归：
递归的方法稍微比较难理解一些。
这里利用LeetCode上一位国人的讲解：

Step 1：Base Case

if(!head || !head->next)
	return head;

可以看到，Base Case的返回条件是当head或者head->next为空，则开始返回。

Step 2：Recurse到底

ListNode *newHead = reverseList(head->next);

在做任何处理之前，我们需要不断的进行递归，知道触及到Base Case。当我们移动到最后一个Node时，就将这个Node定义为newHead，并从newHead开始，重复性的往前更改指针的方向。

Step 3：返回并更改指针的方向

   head->next->next = head;
#2 head->next = NULL;
#3 return newHead;

Reverse Linked List
经过这样的递归后，就可以成功的将该单链表逆置了。

3，代码实现

迭代：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return head;
        
        ListNode* curr = NULL;
        while(head != nullptr)
        {
            ListNode* next = head->next;
            head->next = curr;
            curr = head;
            head = next;
        }
        return curr;
    }
};

递归：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
        
    }
};

1，题目要求

2，题目思路

3，代码实现

相关推荐