数据结构 — 链表(Linked list)

基本概念 #

单向链表 #

JavaScript #

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

Golang #

type ListNode struct {
	Val  int
	Next *ListNode
}

双向链表 #

双向链表在单向链表节点的基础上增加了指向前一个节点的指针,这样一来,既可以从头节点开始从前往后遍历到尾节点,也可以从尾节点开始从后往前遍历到头节点。

环形链表 #

如果把链表尾节点指向下一个节点的指针指向链表的头节点,那么此时链表就变成一个环形链表(也叫循环链表),相当于链表的所有节点都位于一个环中。环形链表既可以是单向链表也可以是双向链表。

141. 环形链表

142. 环形链表 II(链表中环的入口节点)✅

环形链表优先考虑用快慢指针解决。

有序链表 #

83. 删除排序链表中的重复元素 需要将 pre 节点和 curr 节点做比较。

148. 排序链表

相交链表 #

160. 相交链表

回文链表 #

234. 回文链表 解法有:

  1. 将值复制到数组用前后双指针对比。
  2. 递归,参考反转链表的递归思路。
  3. 入栈和出栈。

链表操作 #

一般使用一个哨兵结点来进行链表的遍历。

void addLast(int x) {
    if (first == null) {   //需要判断头节点是否存在
    	first = new Node(x, null);
        return;
    }
    Node p = first;
    while (p.next != null) { //如果头结点存在,则不断的找到尾节点,并将当前的节点添加至尾部
        p = p.next;
    }
    p.next = new Node(x, null);
}

插入元素 #

删除元素 #

遍历链表 #

反转链表 #

206. 反转链表 感觉是个必须得会的题。。

看到题目基本能知道有两种思路,一种是按顺序遍历链表,逐个更新 next 结点,另一种就是利用递归入栈,从最后一个结点开始反向出栈更新 next。

方法一:迭代

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil{
        return head
    }
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

方法二:递归

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    last := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}

进阶练习 92. 反转链表 II

旋转链表 #

61. 旋转链表

思路:

  1. 简化 k 的旋转计算
  2. 将链表闭合为环
  3. 旋转 K 下即为头节点的 next 迭代次数。
  4. 找到头节点,将环分开。

合并链表 #

21. 合并两个有序链表

递归解法

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

迭代解法

需要一个哑结点 dummy,最后返回 dummy.next 即可。

var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode(0)
    let prev = dummy
    while(list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            prev.next = list1
            list1 = list1.next
        } else {
            prev.next = list2
            list2 = list2.next
        }
        prev = prev.next
    }

    if (list1 === null) {
        prev.next = list2
    } else {
        prev.next = list1
    }

    return dummy.next
};

方法技巧 #

快慢指针 #

快慢指针方法也被称为 Hare & Tortoise 算法,该算法会使用两个在数组(或序列/链表)中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。

设两个指针,fast 和 slow,fast 指针每次移动两格, slow 指针每次移动一格, 如果存在环路, 则 fast 最终一定会和 slow 相遇。

141. 环形链表

var hasCycle = function(head) {
    let fast = head
    let slow = head
    while(fast !== null) {
        fast = fast.next
        if (fast !== null) {
            fast = fast.next
        }else {
            return false
        }
        slow = slow.next
        if (slow === fast) {
            return true
        }
    }
    return false
};

哑结点(虚拟头) #

当需要对头结点操作时,可以考虑使用哑结点(dummy node),即创建一个新的结点,并使 dummy.next = head 指向头结点,这样可以避免处理头结点为空的边界问题。

可以参考下面 前后指针 19. 删除链表的倒数第 N 个结点 这个题。

前后指针 #

前后指针区别于快慢指针,两个指针步伐通常一致。

19. 删除链表的倒数第 N 个结点

var removeNthFromEnd = function(head, n) {
    let tail = head
    let dummy = new ListNode(0, head)
    let prev = dummy

    for (let i = 0; i < n; i ++) {
        tail = tail.next
    }

    while (tail !== null) {
        tail = tail.next
        prev = prev.next
    }

    prev.next = prev.next.next
    return dummy.next
};

其它题型 #

86. 分隔链表

138. 复制带随机指针的链表

143. 重排链表

445. 两数相加 II

参考 #

几乎刷完了力扣所有的链表题,我发现了这些东西。。。

本文共 1320 字,上次修改于 Jan 28, 2024
相关标签: 算法, 数据结构