[数据结构与算法]链表练习题目：反转链表

NC78 反转链表

给出一个长度为n链表，反转链表中的所有节点。

比如，输入一个长度为 $n$ 链表：
$$N_1\to N_2\to ...\to N_{n?1}\to N_n$$

翻转后为：
$$N_n\to N_{n?1}\to ...\to N_2\to N_1$$

链表的反转不同于数组：数组反转只需交换数据，链表反转一般要求交换指针域。

比如，一个长度为 4 的链表，如下所示：

反转之后变为：

不难发现，数据在内存中的位置没有改变，只是指针域的值发生了变化。

头插法

头插法，常用的链表构造方法之一。顾名思义，就是把元素插在链表最前边的位置。

首先，我们先声明一个空指针作为头结点，表示此时链表中没有节点：

struct Node {
	int data = 0;
	Node *next = nullptr;
};
Node *head = nullptr;

接下来，从数据源读取数据，假设我们从标准输入读取：

for (int x; cin >> x;) {
	// do something
}

每读入一份数据 $x$，就将其存入一个新节点 $tmp$ ：

for (int x; cin >> x;) {
	Node *tmp = new Node();
	tmp->data = x;
	// do something
}

现在我们有了两个指针 $tmp$ 和 $head$：

• $tmp$ 指向一个孤立的节点。
• $head$ 指向一个链表的头结点。

现在要将 $tmp$ 插入至链表中，头插法的流程是：

• 将 $tmp$ 的指针域指向链表的头结点:

  tmp->next = head;
  

• $head$ 指向 $tmp$ 指向的节点，即将该节点当做新的头结点：

  head = tmp;
  

至此，一次头插法的操作完成啦。可以结合下面的图，更容易理解一点。

按照上述步骤，继续插入第二个节点：

不难发现，按照头插法构造链表，后插入的节点在前面，先插入的节点后面。

因此，我们只要从头至尾遍历输入的链表，然后将每个节点依次按照头插法插入新链表。

最后，新链表就是反转之后的样子啦。

完整代码如下：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *head = nullptr;
        while (pHead != nullptr) {
            auto tmp = pHead->next;
            pHead->next = head;
            head = pHead;
            pHead = tmp;
        }
        return head;
    }
};