LeetCode
迭代(双指针)
pre 和 cur 两个指针,怎么理解? pre 和 cur 是两个普通的JS变量,但是变量的值存的是对象的地址(链表节点)。
typescript
var reverseList = function(head) {
// 1. 初始化,cur指向head, pre指向null
let cur = head
let pre = null
// 2. 确认循环终止条件
while(cur !== null){
// a. 临时变量存 cur.next
let tmp = cur.next
// b. 反转链表节点
cur.next = pre
// c. 两个指针向右移动,注意先pre = cur !
pre = cur
cur = tmp
}
return pre
};
递归写法
typescript
// 1. 初始化,head 给 cur, null给 pre
var reverse = function (pre, cur) {
// 2. 终止条件
if (cur === null) return pre
let tmp = cur.next // A.
cur.next = pre // B. 一定是先A后B
// 函数的参数传递,是从左到右的,pre = cur, cur = tmp
return reverse(cur, tmp)
}
var reverseList = function (head) {
return reverse(null, head)
}
为什么下面这种也可以?
typescript
// 定义 reverse 函数
var reverse = function (cur, pre) {
if (cur === null) return pre
let tmp = cur.next
cur.next = pre
// 传递到后一个时,cur = tmp 引用值, pre = cur 引用值
// 函数参数传递是值传递,所以这里顺序不影响了?!
return reverse(tmp, cur)
// 如果参数是引用类型,那么这个副本实际上是原引用的一个复制,
// 也就是说函数接收的其实是引用的地址
}
// 定义 reverseList 函数
var reverseList = function (head) {
return reverse(head, null)
}
PS JS中的链表
typescript
// 链表节点的类
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
// ListNode 就是一个最简单的链表节点,val 是节点的值,
// next 是一个指向下一个节点的引用。
创建一个包含已知值的链表
typescript
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
console.log(node1.val); // 输出:1
console.log(node1.next.val); // 输出:2
console.log(node1.next.next.val); // 输出:3
在链表中,让 pre 和 cur 指针指向不同的节点非常简单,只需要将它们赋值为对应节点即可。 如果要让 pre 指向 node1,cur 指向 node2,可以这么写:
typescript
let pre = node1;
let cur = node2;
注意 pre 和 cur 现在实际上并没有创建任何新的节点,它们只是创建了一个新的引用,指向了已经存在的节点。