【算法题】反转链表（头插法、C++实现、力扣第206题、剑指offer第24题）

该算法用头插法解决，如果有优化该头插法的方式，欢迎评论区讨论分享，谢谢。

题目链接如下：
力扣第206题
剑指offer第24题

头插法处理反转链表（C++实现）

头插法：
顾名思义，就是每次插入到链表中的元素，都放在链表最前方的位置，即放在首元节点的前面，头结点的后面。

算法步骤：
1、新建一个链表，作为反转链表的返回结果；
2、创建一个节点作为新插入结点（即临时变量）；
3、将原来链表中的value值赋值给插入结点；
4、根据头插法
a） 新插入结点的next域指向头结点的next域；
b）将头结点的next域指向新插入结点；
由此完成头插法的操作；
5、将原来链表依次向下遍历，重复第4步头插法的操作；

算法性能分析：
1、优点时间复杂度，不算太高；
2、临时变量申请较多，因此空间复杂度较高。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
		ListNode* L = new ListNode(-1);
		while(head)
		{
			ListNode* tmp = new ListNode(-1);
            tmp->val = head->val;

            tmp->next = L->next;
            L->next = tmp;

            head = head->next;
		}
		return L->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27