题目:
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
代码实现:
/**
* 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* cur = NULL, *pre = head;
while(pre != NULL){
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
}
代码分析:
- 定义两个指针:pre 和 cur;pre 在前,cur 在后;
- 每次让 pre 的 next 指向 cur ,实现一次局部反转;
- 局部反转完成之后, pre 和 cur 同时往前移动一个位置;
- 循环上述过程,直至 pre 到达链表尾部。
如果还不清楚呢,下面将结合代码图示每一步的操作:
初始情况下,cur 定义为空指针,pre 指向头结点 a,t 指向 pre 的 next 结点 b。
第一次循环
执行pre->next = cur;
后,a 结点的 next 结点指向空指针。pre 和 cur 指针后移,分别指向 b 结点和 a 结点。
第二次循环
执行pre->next = cur;
后,b 结点的 next 结点指向 a 结点。pre 和 cur 指针后移,分别指向 c 结点和 b 结点。
第三次循环
执行pre->next = cur;
后,c 结点的 next 结点指向 b 结点。pre 和 cur 指针后移,分别指向 NULL 和 c 结点。
至此,循环结束,cur指向反链表的头节点。