Skip to content

LeetCode

206. 反转链表

image.png

迭代(双指针)

image.png

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)
}

image.png

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 现在实际上并没有创建任何新的节点,它们只是创建了一个新的引用,指向了已经存在的节点。

参考