算法随笔 — 线性表基础 — 链表

于 2021-03-09 20:04:48 发布
阅读量375 收藏
点赞数
分类专栏： 算法 文章标签： 链表 算法 前端 typescript javascript
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/tm_godspeed/article/details/114497771
版权
本文介绍了链表的基本概念，对比了链表与数组的差异，强调了链表在数据存储中的应用场景。文章详细讲解了单链表的两种实现方式，包括对象形式和数组形式，并提供了多个LeetCode链表相关题目进行实战练习，如环形链表的判断、链表反转等，帮助读者深入理解链表操作。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

单链表是什么

已经熟悉单链表概念的读者可以跳至单链表的实现或习题。

链表和数组很像，它们都是线性的存储结构，它们的不同点是数组是用一段连续的内存地址来存储数据，这也是为什么数组可以通过下标来直接访问的原因。

链表是相对松散的线性结构，也就是说链表中每个节点的物理地址可能不是连续的。

数组读取数据的时间复杂度是O(1)，而链表则是O(n)，因为要访问链表的某个节点必须从头开始遍历。

链表中的一个节点可以分为两部分：指针域和数据域。

指针域是用来指向下一个节点的位置，而数据域则是用来存储这个节点表示的数据。

单链表
链表常用场景

  1. 操作系统内的动态内存分配 (一种实现方式)
  2. LRU 缓存淘汰算法
  3. …

单链表的实现

单链表的实现方式主要有两种，通过对象引用的方式和数组方式

1.对象形式

class ListNode {
  val: any
  next: ListNode | null
  constructor(val: any, next: ListNode) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

function checkChain(head: ListNode) {
  let result = ''
  while (head) {
    result += head.val + '->'
    head = head.next
  }
  console.log(result)
}

// main
const head = new ListNode(0, null)
const node1 = new ListNode(1, null)
const node2 = new ListNode(2, null)
const node3 = new ListNode(3, null)

head.next = node1
node1.next = node2
node2.next = node3

checkChain(head) // 0->1->2->3->

2.数组形式

通过双数组实现链表

// @ts-ignore
const data: number[] = new Array(10).fill(0)
// @ts-ignore
const next: number[] = new Array(10).fill(0)

const add = (lastPointer: number, curPointer: number, val: number) => {
  next[lastPointer] = curPointer
  data[curPointer] = val
}

// main
//* 定义头节点
const head = 3
data[3] = 0

//* 添加后续节点
add(3, 5, 1)
add(5, 2, 2)
add(2, 7, 3)
add(7, 9, 100)

//* 遍历链表
let p = head
let result = ''
while (p !== 0) {
  result += `${data[p]}->`
  p = next[p]
}
console.log(result)	// 0->1->2->3->100->

习题

以下是在LeetCode上有关单链表的习题，有条件的读者可以边看边做。

只要是不看答案就写不出来的都不算是掌握了。

===================================

leetCode 141 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。
leetCode141
解题思路:
使用快慢指针，慢指针每次走一步，快指针每次走两步，如果有环，两个指针迟早会指向同一个节点。

由于每次快指针都比慢指针多走一步，所以当两指针都进入环时，每走一次二者的距离都少1。

function hasCycle(head: ListNode | null): boolean {
    if (!head || !head.next) return false
    let slow = head, fast = head
    do {
        slow = slow.next
        fast = fast.next.next
    } while (slow !== fast && fast && fast.next)
    return !!fast && !!fast.next
};

141

===================================

leetCode 142 环形链表2

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

leetCode142
解题思路：
和上题类似，定义快慢指针，先找到二者相遇的节点

接着先给出一个结论，此时让慢指针回到链头，慢指针和快指针距离环的起点的距离是相等的

接下来解释这个结论是怎么得出的

环形链表起点
结合上图所给条件，又知快指针的步长是慢指针的两倍，所以
2 ( a + b ) = a + b + n ( b + c ) a = ( n − 1 ) b + n c a = ( n − 1 ) ( b + c ) + c ∵ ( n − 1 ) 为 圈 数 ， 直 接 忽 略 不 计 ∴ a = c 2(a+b)=a+b+n(b+c)\\ a=(n-1)b+nc\\ a=(n-1)(b+c)+c\\ \because (n-1)为圈数，直接忽略不计\\ \therefore a = c 2(a+b)=a+b+n(b+c)a=(n−1)b+nca=(n−1)(b+c)+c∵(n−1)为圈数，直接忽略不计∴a=c

有了以上结论之后解题步骤就清晰了

  1. 找到快慢指针的相遇点(和上题一样的做法)
  2. 让慢指针回到链头
  3. 让快慢指针以每次单位1的步长前进，直到二者相遇为止
function detectCycle(head: ListNode | null): ListNode | null {
	if (!head || !head.next) return null
	//* 1.先找到相遇点
	let slow = head, fast = head
	do {
		slow = slow.next
		fast = fast.next.next
	} while (slow !== fast && fast && fast.next)
	if (!fast || !fast.next) return null
	//* 2.让慢指针回到链头
	slow = head
	//* 3.使两指针步长都为1，当两指针相遇时即为链环的起点
	while (slow !== fast) {
		slow = slow.next
		fast = fast.next
	}
	return fast
};

142

===================================

leetCode 202 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

输入：n = 2
输出：false

解题思路：
其实快乐数就是一个判断链表是否有闭环的问题，当有闭环时说明这个数不是快乐数，否则就是。

所以解题思路和 leetCode 141 题是一样的。

function isHappy(n: number): boolean {
	let slow = n, fast = n
	do {
		slow = getNext(slow)
		fast = getNext(getNext(fast))
	} while (slow !== fast && fast !== 1)
	return fast === 1
}
function getNext(num: number) {
	return String(num).split('').reduce((sum, cur) => sum + Math.pow(Number(cur), 2), 0)
}

202
当然，如果笔者使用的是js的话，getNext()可以写作

function getNext(num) {
	return String(num).split('').reduce((sum, cur) => sum + cur * cur, 0)
}

因为两个操作数进行 * 操作的时候会将二者隐式类型转换为数字类型

===================================

leetCode 206 反转链表

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

解题思路：
本题有两个解法：三指针和递归

先说三指针：

  1. 定义三个指针，pre cur next
  2. 初始 pre 指向 null， cur 指向头节点，next指向头节点的下一节点
  3. 以 cur 为参考开始遍历整个链表，每次遍历操作如下
    1. cur 指向 pre
    2. pre 移动到 cur 所处节点
    3. cur 移动到 next 所处节点
    4. next 移动到 next 的下一节点
function reverseList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head
    let pre = null, cur = head, next = head.next
    while (cur) {
        cur.next = pre
        pre = cur
        cur = next
        if (next) next = next.next
    }
    return pre
};

206-1

递归：

递归的真谛就是甩锅，自己做不到的事就交给别人做，每次(每个作用域)只解决一个具体的问题

在本题中，每次作用域要做的事情就是将下一节点指向自己，最后返回反转后的头节点

以笔者的文字功底，很难将递归描述清楚，所以接下来我会先给出代码，再把图画出，至于能不能看懂，就要看你的悟性了

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head
  const tail = head.next, p = reverseList(head.next)
  head.next = tail.next
  tail.next = head
  return p
}

206-2
反转链表1
反转链表2

===================================

leetCode 92 反转链表II

反转从位置m到n的链表。请使用一次遍历完成反转。

1 ≤ m ≤ n ≤ 链表长度
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路分析：
由于本题可能会对链头进行操作，因此需要插入虚拟头节点

反转区间节点链表2

  1. 插入虚拟头节点
  2. 令指针P指向第一个待反转节点的前一位
  3. 利用上题的方式进行反转链表，注意次数为 n - m + 1
  4. 将指针P指向反转链表后的头节点
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
	if (!head || !head.next) return head
	const virtualHead = new ListNode(null, head)
	let p = virtualHead
	const cnt = right - left + 1
	// 使p指针移动到第一个待反转节点的前一个节点
	while (--left) {
		p = p.next
	}
	// 开始反转节点，并使p的next指向反转后链表的头节点
	p.next = reverseN(p.next, cnt)
	return virtualHead.next
};

function reverseN(node: ListNode | null, cnt: number): ListNode | null {
	if (cnt === 1) return node
	const tail = node.next
	const p = reverseN(node.next, cnt - 1)
	node.next = tail.next
	tail.next = node
	return p
}

92

===================================

leetCode 25 K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

  1. 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  2. 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]

输入：head = [1], k = 1
输出：[1]

解题思路：

  1. 原链表插入虚拟头节点，并定义p、q两个指针
    25题解
    p 指向待操作组的头节点的前一位
    q 指向待操作组的头节点
  2. 每次在反转链表前先让q指针判断待操作组数量够不够n个
    1. 够，执行反转链表操作
    2. 不够，返回传入头节点
  3. 当进行了链表反转操作后，q指针 指向了反转后链表的尾节点，此时让 p指针 移动到 q指针 的位置，q指针移向下一位
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
	if (head === null || head.next === null) return head
	const virtualHead = new ListNode(0, head)
	let p = virtualHead, q = head
	while ((p.next = reverseN(q, k)) !== q) { // 该条件成立说明执行了反转操作
		p = q
		q = q.next
	}
	return virtualHead.next
};

function reverseN(node: ListNode, n: number): ListNode {
	let p = node
	const cnt = n
	while (--n && p) p = p.next
	if (p === null) return node // 不足n个
	return _reverseN(node, cnt)
}

function _reverseN(node: ListNode, n: number): ListNode {
	if (n === 1) return node
	const tail = node.next,
		p = _reverseN(node.next, n - 1)
	node.next = tail.next
	tail.next = node
	return p
}

25

===================================

leetCode 61 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解题思路：

  1. 定义 指针p 指向头节点，遍历到尾节点，然后使尾节点指向头节点形成闭环
  2. 令链表长度为L，使 指针p 走 L-(k % L) 步
  3. 此时，指针p 所指位置为新链表的尾节点，所指的后一位为新链表的头节点
    旋转链表题解
    循环右移时指针移动步数: L - (k % L)
    循环左移时指针移动步数: k % L (模仿上图自行推断)
function rotateRight(head: ListNode | null, k: number): ListNode | null {
	if (head === null || head.next === null || !k) return head
	let p = head, length = 1
	while (p.next !== null) {
		p = p.next
		length++
	}
	p.next = head
	let cnt = length - (k % length)
	while (cnt--) p = p.next
	const newHead = p.next
	p.next = null
	return newHead
};

61

===================================

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

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

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

输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = []
输出：[]

输入：head = [1]
输出：[1]

解题思路：
这题就是上述 leetCode 25 的一个特殊案例，在那道题中令 k = 2 即可得到这道题的答案。

具体过程就不再复述了，不清楚的同学可以回到上面重新学习。

function swapPairs(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head
    const virtualHead = new ListNode(null, head)
    let p = virtualHead, q = head
    while ((p.next = reverseN(q, 2)) !== q) {
        p = q
        q = q.next
    }
    return virtualHead.next
};

function reverseN (node: ListNode, n: number): ListNode {
    const cnt = n
    let p = node
    while (--n && p) {
        p = p.next
    }
    if (!p) return node
    return _reverseN(node, cnt)
}

function _reverseN (node: ListNode, cnt: number): ListNode {
    if (cnt === 1) return node
    const tail = node.next
    const p = _reverseN(node.next, cnt - 1)
    node.next = tail.next
    tail.next = node
    return p
}

24

===================================

leetCode 19 删除链表的倒数第n个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

解题思路：

链表要删除第n个节点，就要先找到第 n - 1 个节点在哪

使用双指针法就能很快解出本题

  1. 往原链表添加虚拟头节点 (因为有可能会变更头节点)
  2. 定义慢指针指向虚拟头节点，快指针指向头节点
  3. 快指针往后走n步
  4. 快慢指针同时向后走，直到快指针到尾节点
  5. 此时慢指针就到被删除节点的前一个节点了
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    if (!head) return null
    const virtualHead = new ListNode(null, head)
    let slow = virtualHead, quick = head
    while (--n && quick.next) {
        quick = quick.next
    }
    while (quick.next) {
        slow = slow.next
        quick = quick.next
    }
    slow.next = slow.next.next
    return virtualHead.next
};

19

===================================

leetCode 83 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

输入: 1->1->2
输出: 1->2

输入: 1->1->2->3->3
输出: 1->2->3

解题思路：
—— 快慢指针

  1. 定义快慢指针同时指向头节点
  2. 使快指针一直往后走，直到与慢指针代表的值不同
  3. 使 慢指针的next 指向 快指针
  4. 使慢指针移动到快指针的位置
  5. 重复以上步骤直到慢指针到尾节点
function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (!head) return null
    let slow = head, fast = head
    while (slow) {
        while (fast && slow.val === fast.val) {
            fast = fast.next
        }
        slow.next = fast
        slow = fast
    }
    return head
};

83-1
—— 单指针

  1. 定义一个指针指向链头，遍历到链尾
  2. 每次遍历的时候判断下一节点的val是否和当前节点的相等，如果不等使 当前节点的next 指向下下个节点
function deleteDuplicates(head: ListNode | null): ListNode | null {
   if (head === null) return null
   let p = head
   while (p.next) {
       if (p.val === p.next.val) {
           p.next = p.next.next
           continue
       }
       p = p.next
   }
   return head
};

83-2

===================================

leetCode 82 删除排序链表中的重复元素

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

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

输入: 1->1->1->2->3
输出: 2->3

解题思路：

  1. 因为这题又有可能操作头节点，所以需要插入虚拟头节点
  2. 剩下的解题思路和上题基本相似，但是这题只能用双指针，因为删除节点必须要找到被删除节点的前一个节点，在本题的情况下只能用双指针才更加方便
function deleteDuplicates(head: ListNode | null): ListNode | null {
	if (head === null || head.next === null) return head
	const virtualHead = new ListNode(null, head)
	let p = virtualHead, q = p
	while (p.next) {
		if (p.next.next && p.next.next.val === p.next.val) {
			q = p.next.next
			while (q && q.val === p.next.val) q = q.next
			p.next = q
			continue
		}
		p = p.next
	}
	return virtualHead.next
};

82

结语

创作不易，如果本文对你有帮助，请点一个免费的赞鼓励一下。如果本文有错误或者你有更好的想法，欢迎评论区评论~

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值