题解 | #反转链表#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if (pHead == nullptr) {
			return nullptr;
		}
		ListNode * pre = nullptr;
		ListNode * now = pHead;
		ListNode * next = nullptr;

		while (now != nullptr) {
			next = now->next;
			now->next = pre;
			pre = now;
			now = next;
		}

		return pre;
    }
};

单链表反转，一般都是通过多个指针辅助，将节点的next指针指向前一个节点。关键在于当前节点如果直接改变了next指针的指向，则会丢失掉该节点next指针原本指向的节点，故所以需要借助额外的临时指针变量保存原本的next指向的节点。

还有另外一种实现，利用递归实现反转链表：

node* ReverseList(node* pHead) {

    if (pHead == nullptr || pHead->next == nullptr)

        return pHead;

    node * temp = ReverseList(pHead->next);

    pHead->next->next = pHead;

    pHead->next = nullptr;

    return temp;

}

传入头节点，通过递归返回最后一个节点的地址，然后在递归函数中一个个将节点的next指向反转