链表及练习

2023/3/2

数据结构

- 概念

链表：是多个元素组成的列表，元素不连续，用 next 指针连在一起
数组与链表的区别：数组增删非首尾元素时需要移动元素；链表增删非首尾元素时不需要移动元素，只需要修改 next 的指向即可

链表实现：

const a = {val:'a'};
const b = {val:'b'};
const c = {val:'c'};
const d = {val:'d'};
a.next = b;
b.next = c;
c.next = d;

//遍历链表
let p = a;
while(p){
    console.log(p.val);
    p = p.next;
}

//链表插入值
const e = {val:'e'}
c.next = e;
e.next = d;

//删除e节点
c.next = d;

- 链表练习

leetcode237 删除链表中的节点

解题思路：题目中指的删除节点并不是从内存中删除它，而是指给定结点的值不再存在于链表中。因为无法获取当前节点的前一个节点，可以让被删除节点的值变为它的下一个节点，然后删除它的下一节点，例如1，2，3，4要删除3，可以先将链表变为1，2，4，4，然后再删除第二个4，变为1，2，4即可达到目的。

题目代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @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;
};

leetcode206 反转列表

解题思路：双指针遍历链表，指针p1，p2，

题目代码：p1指向链表前一位，取出链表后一位，令p1指向p2，然后交换p1和p2位置。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1){
        let temp = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = temp;
    }
    return p2;
};

leetcode2 两数相加

解题思路：创建一个新链表，遍历原链表，存储每一位的相加值和进位，最后处理进位。

解题代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0);
    let p1 = l1;
    let p2 = l2;
    let p3 = l3;
    let carry = 0;
    while(p1||p2){
        let v1 = p1?p1.val:0;
        let v2 = p2?p2.val:0;
        let val = v1+v2+carry;
        carry = Math.floor(val/10);
        p3.next = new ListNode(val%10);
        if(p1) p1 = p1.next;
        if(p2) p2 = p2.next;
        p3 = p3.next; 
    }
    //处理最后一位进位
    if(carry){
        p3.next = new ListNode(carry);
    }
    //因为头部一开始定义了一个节点，所以返回l3.next
    return l3.next;
};

leetcode83 删除排序列表中的重复元素

解题思路：由于是排序列表，所以重复元素一定相邻，直接删除即可。遍历链表，如果当前和下一个相同，就删除下一个，否则遍历下一个元素。

解题代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next){
        if(p.val == p.next.val){
            p.next = p.next.next;
        }
        else p = p.next;
    }
    return head;
};

leetcode141 环形链表

解题思路：快慢指针法，当两个指针均不为空时，若存在环路，则两个指针终会相遇，若不相遇则不存在环路。

解题代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p1 = head;
    let p2 = head;
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2){
            return true;
        }
    }
    return false;
};

LOADING...

链表及练习

- 概念

- 链表练习