题目描述

输入一个链表,反转链表后,输出新链表的表头。
示例1
输入
复制
{1,2,3}
返回值
复制
{3,2,1}

题解:

如果用偷懒的方法,可以用vector来存链表内容,然后来个翻转(vector自带)即可
但是,我们不可能光靠这种方法,来讲一下正解
在这里插入图片描述
通过图我们可以看出,其实翻转链表,也就是将指向翻转
所以我们需要一个链表s作为存新数据(也就是翻转后的数据)
还需要一个q作为中间变量
链表p为题目所给的pHead
步骤:
先用q存p的下一个节点的地址,这样是因为后续p有其他操作,如果不提前保存会丢失
然后将p->next=s,将当前节点与链表中断,并指向s
然后将s=p,
这两步操作可以理解为,将当前节点从原链表中取出,并将下一个节点指向当前节点(相当于调转了箭头方向)
从原本的
p ---> p->next
变成了
p->next ---->p
然后这个是存在s内的
最后将p=q,相当于原本暂存的东西还给p,使得p的后续没有发生改变

代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)return NULL;
            ListNode * p=pHead;
        ListNode * s=NULL;
        ListNode * q=NULL;
        while(p!=NULL)
        {
            q=p->next;//先用q来记录下一个节点的地址
            p->next=s;//让当前节点与链表中断,并指向前一个节点s
            s=p;//s指向当前节点
            p=q;//p指向q,而q存的是下一个节点的地址

        }
        return s;
    }
};