茂名中小企业网站制作,图书销售网站建设,注册wordpress账号,辽宁建设工程信息网网站前言
反转单向链表就是将整个单链表的数据进行倒序的过程。
例如#xff0c;如果反转之前的单链表是0-1-2-3#xff0c;那么反转之后的单链表应该是3-2-1-0。这个操作通常是通过改变链表中每个节点的指针方向来实现的#xff0c;即让每个节点的指…前言
反转单向链表就是将整个单链表的数据进行倒序的过程。
例如如果反转之前的单链表是0-1-2-3那么反转之后的单链表应该是3-2-1-0。这个操作通常是通过改变链表中每个节点的指针方向来实现的即让每个节点的指针指向其前一个节点而不是下一个节点。这种操作不需要开辟新的内存空间只需要通过改变指针的指向即可完成。
实现原理
在反转单向链表的过程中通常需要使用三个指针分别是指向当前节点的指针指向当前节点前一个节点的指针以及临时存储当前节点下一个节点的指针。然后从链表的第二个节点开始遍历将当前节点的指针指向前一个节点同时更新前一个节点和下一个节点的指针直到遍历到链表的最后一个节点此时整个链表就被反转了。 代码实现
步骤1
首先定义两个指针指向当前节点以及指向当前节点前一个节点。
let current head;let prev null;
步骤2
定义记录 p1 指针的next的临时指针
const nextTemp current.next;
步骤3
然后我们编写一个函数来反转链表
function reverseLinkedList(head) { let prev null; // 前一个节点初始化为null let current head; // 当前节点从链表的头节点开始 while (current ! null) { // 保存当前节点的下一个节点 const nextTemp current.next; // 修改当前节点的next指向prev current.next prev; // 将prev和current向前移动一步 prev current; current nextTemp; } // 反转后原链表的头节点成为尾节点其值为null // 新的头节点是prev return prev;
}
方法的使用
定义一个链表节点类
class ListNode { constructor(val, next null) { this.val val; this.next next; }
}
接下来我们可以创建一些节点并连接它们来形成一个链表然后调用 reverseLinkedList 函数来反转这个链表
// 创建链表: 1 - 2 - 3
const node3 new ListNode(3);
const node2 new ListNode(2, node3);
const node1 new ListNode(1, node2); // 打印原始链表
let current node1;
while (current ! null) { console.log(current.val); current current.next;
} // 打印结果1 2 3// 反转链表
const reversedHead reverseLinkedList(node1); // 打印反转后的链表
current reversedHead;
while (current ! null) { console.log(current.val); current current.next;
}
// 打印结果3 2 1
