链表相连与变量赋值时的内存变化 —— 链表复制与逆序的实现

2019/06/01 15:39
阅读数 7

在对链表进行一些复杂的操作时,尤其是对链表实际使用不是很多的人很容易出现错误。

比如,在对一个链表进行反转时:我们可以定义一个额外的链表将原链表数据依次倒序保存起来,但是这样空间的复杂度并不是最优的。而如果能很好的运用链表的一些常规操作,即可实现时间与空间复杂度最优。

下图是链表在进行连接与变量赋值时,内存上的一些变化:

 

了解了内存变化,那么我们便可以对链表的赋值与反转很容易的实现了:

首先,定义一个链表 node1,它由 3个节点组成

function ListNode(val){
  this.val = val;
  this.next = null;
}
let node1 = new ListNode(1);
let node2 = new ListNode(3);
let node3 = new ListNode(5);
node1.next = node2;
node2.next = node3;

那么,对链表的复制操作如下:

/* 复制 */
function copy(head) {
  let new_head = new ListNode(0);
  let head_ptr = new_head;
  while (head) {
    head_ptr.next = head;
    head_ptr = head; // 移动 head_ptr
    head = head.next;
  }
  return new_head.next
}

console.log(copy(node1))

 反转操作如下:

/* 逆序 */
function copy(head) {
  let new_head = null;
  while (head) {
    let next = head.next;
    head.next = new_head;
    new_head = head;
    head = next;
  }
  return new_head
}

console.log(copy(node1))

 

通过掌握这些链表的常规操作,相信再去解答关于链表题目将会变得很容易了!

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部