解题思路:首先判断给定的链表head是否为空指针或只包含一个节点。如果满足条件,则直接返回当前的头结点head。
定义两个指针p和q,分别指向当前节点和下一个节点。初始时,p指向头结点,q指向当前节点的下一个节点。
进入循环,当q不为空时,定义一个指针o,指向q的下一个节点。
将q的next指针指向p,即改变指针方向,使q指向p。
更新p和q的值,使p指向q,q指o。
循环结束后,链表中的节点指针方向已全部改变,最后一个节点成为新的头结点,即p成为新的头指针。
将原头结点head的next指针置为NULL,将其变成新的尾结点。
返回新的头指针p,即为翻转后的链表的头结点。
/**
* 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; // 空指针或一个结点不用翻转,直接返回head
ListNode* p = head; // p表示当前节点
ListNode* q = p->next; // q表示下一个节点
while (q) { // 当q不为空指针时
ListNode* o = q->next; // o表示q的下一个节点
q->next = p; // 改变指针方向,令q指向p
p = q; // 向后移动,逐个改变方向。
q = o;
}
head->next = NULL; // head变成新的尾节点。
return p; // p变成新的头指针。
}
};