[第28期] 回顾一下常见的链表操作

皮小蛋

发布于 2020-03-02 10:50:05

3190

发布于 2020-03-02 10:50:05

文章被收录于专栏：前端皮小蛋前端皮小蛋

背景

最近一直在整理上周参加的管理培训的东西，已经写好了，内容太长，不太适合发到公众号里，我发到了思否上，感兴趣的朋友可以看看。

https://segmentfault.com/a/1190000021273540

正文

我们都知道，数据结构和算法，是一个工程师必须要掌握好的一部分，也是平时比较容易忽视的一个环节。

要学好这部分，需要3分理论， 7分实践。

恰好下午我翻阅之前提交记录的时候，看到了这部分，今天就分享一下几道题，回顾下列表的基本操作。

希望能给大家一些帮助。

#237 删除列表中某个节点

这是最基础的一道题了。

题目描述：

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

输入: head = [4,5,1,9], node = 5

输出: [4,1,9]

解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，

该链表应变为 4 -> 1 -> 9.

即：要删除5这个节点：

动态示意图：

弄明白过程之后就很容易实现了：

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

还有一点知识需要特别注意：

JS中基本类型按值引用，对象类型按地址引用：

let a = {};
let b = a;
a.val = 1; // 此时 a → { val: 1 }, b → { val, 1 }
a = {}; // 此时 a → {}, b → { val, 1 }

在JS中，以上代码段中的a其实只是保存了一个内存中的地址，每次使用a的时候其实是通过地址去找到真正的{}。

而将a赋值给b，其实就是将a保存的地址复制给b一份，然后调用b也会去找到和a相同地址的{}。

a.val = 1就是将a地址指向的对象{}增加一个值为1的属性val。

因为b保存的地址也指向同一个对象，所以看起来就像是b也在同步变化。其实b保存的地址并没有变化。

a = {}则将一个新的{}的地址赋值给了a，此时覆盖掉了原来保存的{ val: 1 }对象的地址，然而b所保存的地址仍然指向原来的 { val: 1 }

放到本题来说就是题目给的参数node（相当于示例中的b），只是题意链表中的对应节点（相当于示例中的a）的地址副本，对node（b）赋值相当于直接覆盖掉这个副本的值，但是原节点（a）保存的地址并不会变。

对 node.next 和 node.val赋值才是真正的操作链表对应节点的内容。

#206 反转列表

反转一个单链表。

这道题，几乎是链表的必考题，微信的笔试题中就有这道题。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

动画演示：

题解：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    var pre = null;
    var cur = head;
    
    while(cur !== null) {
        var temp = cur.next;
        cur.next = pre
        pre = cur
        cur = temp        
    }    
    return pre
};

Python 实现：

#24 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

动画演示：

题解：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let tempHead = new ListNode(0)
    tempHead.next = head
    let prev = tempHead

    while(prev.next && prev.next.next) {
        let a = prev.next
        let b = a.next
        prev.next = a.next
        a.next = b.next
        b.next = a
        prev = a
    }
    
    return tempHead.next
};