题目描述

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

方法1：改变指向

思路如下：

初始化

好的，假如我们要让q指向p，那么q的下一个结点就没办法找到了，就会出现断链的情况，如图

所以，在每次循环的时候，都额外需要一个指针r，去指向q的下一个结点

此时开始反转，让后一节点链接前一结点


开始第二次循环，此时r又可以指向q的下一结点。

/*
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 *q = pHead->next;
        pHead->next = NULL;
        ListNode *r;
        
        while(q) {
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        
        pHead = p;
        return pHead;
    }
};

方法2：从原链表的头部开始逐个取结点并插入到新链表的头部

①初始化

1）第一轮

②备份下一结点，令第一个结点的指针域为空

③让pNew指向p所指向的结点，让p指向p的下一结点

2）第二轮

备份下一结点

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pNew = NULL;	// 新链表
        ListNode *p = pHead;
        
        while(p) {
            ListNode *tmp = p->next;	// tmp保存下一个结点
            p->next = pNew;
            pNew = p;					// 让pNew指向p指向的结点
            p = tmp;
        }
        
        return pNew;
    }
};

方法3：利用栈实现

由于栈是后入先出的，于是考虑用栈实现。
① 首先把链表的元素逐个压入栈中

此时链表依然是这样的

那么我们需要另外一个指针，也指向第一个结点，然后开始逐个修改里面的值


在执行完上述循环后，q指向的结点的指针域为空了，此时pHead指向的链表所有元素均已修改，于是返回pHead即可

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        std::stack<int> st;
        ListNode* p = pHead;
        while(p) {
            st.push(p->val);
            p = p->next;
        }
        
        ListNode* q = pHead;
        while(q) {
            q->val = st.top();
            st.pop();
            q = q->next;
        }
        
        return pHead;
    }
};