逆置链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

答案

/*

struct ListNode {

int val;

struct ListNode *next;

ListNode(int x) :

val(x), next(NULL) {

}

};*/

class Solution {

public:

    ListNode* ReverseList(ListNode* pHead) {

        ListNode *pre = nullptr;

        ListNode *cur = pHead;

        ListNode *nex = nullptr;

        while(cur){

            nex=cur->next;

            cur->next=pre;

            pre=cur;

            cur=nex;

        }

        

return pre;

    }

};

解释一下​：

逆置链表的过程类似于公路上一列排列整齐的汽车全部原地掉头​；

对于链表的每个节点来说，可以理解为节点的“箭头（指针）”方向发生了变化；

cur->next=pre;

//改变当前的指针方向

 pre=cur;

//为下一个节点做准备​，当前节点要变成下一个节点的前节点了​；

 cur=下一个节点;

//为下一个节点做准备，当前节点向后滑动一个，这时候发现cur的next需要提前保存一次的

 

完整答案​：​
 

    ​    ​    ​nex=cur->next;

            cur->next=pre;

            pre=cur;

            cur=nex;