剑指offer24 反转链表
题目
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制: 0 <= 节点个数 <= 5000
思路
双指针
选择双指针迭代的方法。
/**
* 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 *p = head,*pre = NULL;
while(p) {
ListNode *temp = p->next;//暂存当前结点的后继
p->next = pre;
//双指针同时后移
pre = p;
p =temp;
}
return pre;
}
};
遍历聊表,使用pre指针指向当前结点的上一个结点,改变指针指向,让结点指向pre带便的结点,可以由此完成反转。
- 用temp指针存储当前结点p的后继
- 当前结点p指向pre也就是当前结点P的前驱(初始为空)
- pre和p一起后移
- 最后一次后移时,p指向了空,pre指向了最后一个结点,返回pre就行了 一张图可以很好的理解:
递归
递归与前一种方法本质是相同的,不过他用递归完成了指针后移
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* df(ListNode *p,ListNode *pre) {
if(p == NULL) return pre;
ListNode *temp = p->next;//暂存一下p的后继
p->next = pre;
return df(temp,p);
}
ListNode* reverseList(ListNode* head) {
return df(head,NULL);//相当于进行了初始化,ListNode* cur = head,*pre = NULL;
}
};
使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点pre,每次递归时都改变一下结点指针的方向就行了。当然也可以先递归寻找结点,再从链表末尾开始每一层递归中修改指针方向,这样递归写法就不同了。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
return df(head, NULL); // 调用递归并返回
}
ListNode* df(ListNode *p, ListNode *pre) {
if (p == NULL) return pre; // 终止条件
ListNode* temp = df(p->next, p); // 递归后继节点
p->next = pre;// 修改节点引用指向
return temp;// 返回反转链表的头节点
}
};
转载自:https://juejin.cn/post/7032855176071348237