反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

头插法反转解题思路

定义一个新的链表和一个临时节点，遍历原链表并保存每一个节点的next指针，将该节点加入新链表头指针后的一个节点。循环遍历，原链表的最后一个节点即是新链表的第一个有效值节点。

代码

/*** @param {ListNode} head* @return {ListNode}*/
var reverseList = function(head) {let p =head;let q =new ListNode(0);while(p){let x=p.next;p.next = q.nextq.next = p;p=x;}return q.next;
};

迭代解题思路

直接改变每一个指针方向，对原链表每一个指针方向进行改变达到反转链表的效果。在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

代码

/*** @param {ListNode} head* @return {ListNode}*/
var reverseList = function(head) {let tail = null;//首先定义一个尾指针，让它从原链表的头开始依次往前，直到原链表的头指针let p = head;//定义一个p不改变原链表地址while(p){let x = p.next;//保存下一个节点位置p.next = tail;//将本节点的指针指向tail后位链表（新链表该节点之后的链表）tail = p;//赋值tail，使tail添加上本节点形成新的后位链表p = x;//移动p指针，遍历原链表}return tail;
};