本文共 1923 字,大约阅读时间需要 6 分钟。
题目描述:输入一个链表,反转链表后,输出新链表的表头。
先写伪代码,厘清思路:首先我们最终需要的节点是 反转之后的链表头部,也就是当前链表的最后一个节点。我们需要将在当前节点不为空的前提下,执行一个循环操作:下一节点指向前一节点,前一节点指向当前节点,当前节点指向下一节点。循环结束条件:当前节点为空。
while(当前节点不为空){ if(下一个节点是空吗) 若是,则将 反转链表的 头部 指向当前节点,因为已经找到了最后一个节点; 若不是: 下一节点 指向 之前结点; 之前节点 指向 当前节点; 当前节点 指向 下一节点。}return 反转链表的头部;
可见,需要维护四个状态变量,反转头节点,之前节点,当前节点,当前节点的下一节点
。
struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};ListNode* ReverseList(ListNode* head){ // 定义需要维护的三个变量 ListNode* revHead = nullptr; ListNode* preNode = nullptr; ListNode* curNode = head; while(curNode != nullptr){ ListNode* pNext = curNode -> next; if(curNode -> next == nullptr) // 若下节点为空的话,就直接将 反转链表的头 指向当前节点即可,因为后面没有节点了。 revHead = curNode; curNode -> next = preNode; // 下一节点 指向 之前节点; preNode = curNode; // 之前节点 指向 当前节点 curNode = pNext; // 当前节点 指向 下一节点 } return revHead;}// 递归解法 ListNode* reverseList(ListNode* head) { //如果传入的head是NULL,则直接返回NULL (只有第一次调用传NULL才会走到,否则之前就会走到head->next==NULL) //如果传入head满足head->next==NULL,则head是原链表tail,需要返回 if(head==NULL || head->next==NULL){ return head; } //如果没有满足上面的退出条件,下面这个递归调用会一直递归下去,直到找到tail节点,此处返回的就是tail ListNode* tail = reverseList(head->next); //此处的head是每次递归调用的传入参数,以[1,2,3,4,5]为例,此处分别是4,3,2,1 注意没有5,因为5满足退出条件在前面返回了 //head->next指向原链表中当前处理元素的next元素,即head为4时,next为5;head为3时,next为4 //因此此处让next的next指向正在处理的元素,即让5指向4,让4指向3等等 head->next->next = head; //同时正在处理的元素不能再指向以前的next,暂且将其next置空,等到处理到该元素时上面的操作会让其指向原先前面的元素 //但是对于原链表第一个元素1,即这儿最后处理的head,因为没有下面的操作了,所以1的next为NULL,符合要求。 head->next = NULL; /*每次递归返回都是返回同一个tail,即5,同时5也是反转后链表的第一个元素。 这个tail是最后一次递归从退出条件处返回的,然后每次递归返回后都返回给上一层, 最后一次head为1的时候,处理结束,返回这个tail */ return tail; }};
转载地址:http://gmwki.baihongyu.com/