题目描述
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
循环版本解题思路
- 三个指针，直至cur为空为止
- 这样翻转后的头指针为当前为空的节点的前一个节点
/**
* 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* pre = NULL;
ListNode* cur = head;
if(cur == NULL){
return NULL;
}
while(cur){
ListNode* curNext = cur -> next;
cur -> next = pre;
pre = cur;
cur = curNext;
}
head = pre;
return head;
}
};
递归版本解题思路
- 参考链表翻转1链表翻转2
- 对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的：
输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，在来看这个问题。比如说我们想反转这个链表：
- 那么输入 reverse(head) 后，会在这里进行递归： ListNode last = reverse(head.next); 不要跳进递归，而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：
- 这个 reverse(head.next) 执行完成后，整个链表就成了这样：
- 并且根据函数定义，reverse 函数会返回反转之后的头结点，我们用变量 last 接收了。
- 现在再来看下面的代码：
head.next.next = head;
- 接下来：
head.next = null;
return last;
/**
* 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 == NULL || head -> next == NULL){
return head;
}
ListNode* newHead = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return newHead;
}
};
