题目描述
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
样例
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL
要实现链表的反转,在循环迭代时我们需要保存三个量,要反转的前一个结点的指针p,要反转的后一个节点的指针q,以及后一个节点的后一个节点的指针o。保存p,q是因为反转时要有发出->和接受->的对象,保存o是因为当q->next变成p之后,如果不先保存原来的q->next,循环迭代就无法继续了。首先考虑空链表和单个节点的情况,这两种情况都不需要反转,直接返回即可。当节点数大于等于2时,head和head->next都非NULL,循环中每次反转一个节点,并迭代,使p和q指向下一个节点,当q为NULL时结束循环。最后要记得将head->next设为NULL,否则其还保留初值(指向第二个节点)。
C++ 代码
/**
* 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||!head->next) return head;
ListNode* p=head;
ListNode* q=head->next;
while(q){
auto o=q->next;
q->next=p;
p=q;
q=o;
}
head->next=NULL;
return p;
}
};