分类信息系统网站模板,桂林两江四湖属于哪个区,大连小程序定制,智能建造技术专业学什么反转链表
题目
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]示例 2#xff1a; 输入#xff1a;head [1,2]
输出#xff1a;[2,1]示例 3…反转链表
题目
给你单链表的头节点 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 xp.next;p.next q.nextq.next p;px;}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;
};
