本文最后更新于:2024年1月14日 晚上

学而时习,本文记录链表操作相关算法练习笔记。

反转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
last_node = None
current_node = pHead

while current_node is not None:
next_node = current_node.next
current_node.next = last_node
last_node = current_node
current_node = next_node

return last_node

复杂度

时间 空间
O(n) O(1)

解题备注

  • 维护当前节点,顺带考虑前后节点,会比较稳健
  • 设置虚拟前置节点,现场生成后置节点,更加鲁棒,甚至同时囊括了输入为None的情况
  • 需要注意返回前置节点作为新链表头

两个链表是否相交

这个问题有意思,也是力扣第 160 题「相交链表open in new window」函数签名如下:

1
ListNode getIntersectionNode(ListNode headA, ListNode headB);

给你输入两个链表的头结点 headAheadB,这两个链表可能存在相交。

如果相交,你的算法应该返回相交的那个节点;如果没相交,则返回 null。

比如题目给我们举的例子,如果输入的两个链表如下图:

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点,然后和另一条链表对比,但这就需要额外的空间。

如果不用额外的空间,只使用两个指针,你如何做呢?

难点在于,由于两条链表的长度可能不同,两条链表之间的节点无法对应:

如果用两个指针 p1p2 分别在两条链表上前进,并不能同时走到公共节点,也就无法得到相交节点 c1

解决这个问题的关键是,通过某些方式,让 p1p2 能够同时到达相交节点 c1

所以,我们可以让 p1 遍历完链表 A 之后开始遍历链表 B,让 p2 遍历完链表 B 之后开始遍历链表 A,这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接,就可以让 p1p2 同时进入公共部分,也就是同时到达相交节点 c1

那你可能会问,如果说两个链表没有相交点,是否能够正确的返回 null 呢?

这个逻辑可以覆盖这种情况的,相当于 c1 节点是 null 空指针嘛,可以正确返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pa = headA
pb = headB

while pa != pb:
if pa == None and pb == None:
return None
elif pa == None:
pa = headB
pb = pb.next
elif pb == None:
pb = headA
pa = pa.next
else:
pb = pb.next
pa = pa.next
return pa

判断链表是否包含环

判断链表是否包含环属于经典问题了,解决方案也是用快慢指针:

每当慢指针 slow 前进一步,快指针 fast 就前进两步。

如果 fast 最终遇到空指针,说明链表中没有环;如果 fast 最终和 slow 相遇,那肯定是 fast 超过了 slow 一圈,说明链表中含有环。

当然,这个问题还有进阶版,也是力扣第 142 题 环形链表 :如果链表中含有环,如何计算这个环的起点?

可以看到,当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。

为什么要这样呢?这里简单说一下其中的原理。

我们假设快慢指针相遇时,慢指针 slow 走了 k 步,那么快指针 fast 一定走了 2k 步:

fast 一定比 slow 多走了 k 步,这多走的 k 步其实就是 fast 指针在环里转圈圈,所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m,那么结合上图的 slow 指针,环的起点距头结点 head 的距离为 k - m,也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是,如果从相遇点继续前进 k - m 步,也恰好到达环起点。因为结合上图的 fast 指针,从相遇点开始走k步可以转回到相遇点,那走 k - m 步肯定就走到环起点了:

所以,只要我们把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后一定会相遇,相遇之处就是环的起点了。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fake_head = ListNode(0)
fake_head.next = head

fast = fake_head
slow = fake_head

for _ in range(n):
fast = fast.next
while fast.next is not None:
fast = fast.next
slow = slow.next

slow.next = slow.next.next
return fake_head.next

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
fake_head = ListNode(0)
p = fake_head
p1 = list1
p2 = list2
while p1 or p2:
if p1 is None:
p.next = p2
p2 = p2.next
elif p2 is None:
p.next = p1
p1 = p1.next
else:
if p1.val < p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
return fake_head.next

分隔链表

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
large_head = ListNode(0)
small_head = ListNode(0)
large = large_head
small = small_head
p = head
while p is not None:
if p.val < x:
small.next = p
small = p
else:
large.next = p
large = p

p = p.next
small.next = large_head.next
large.next = None

return small_head.next

链表的中间结点

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = head
slow = head
while fast.next is not None:
if fast.next is not None:
fast = fast.next
if fast.next is not None:
fast = fast.next
if slow.next is not None:
slow = slow.next
return slow

合并 K 个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
import heapq

res_fake_head = ListNode(0)
p = res_fake_head
heap = []
for node in lists:
if node:
heapq.heappush(heap, (node.val, node))
node = node.next
while heap:
_, cur_node = heapq.heappop(heap)
p.next = cur_node
p = cur_node
if cur_node.next:
heapq.heappush(heap, (cur_node.next.val, cur_node.next))

return res_fake_head.next

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head

p = head
q = head.next
head.next = None
while q is not None:
r = q.next
q.next = p
p = q
q = r
return p

92. 反转链表 II

给你单链表的头指针 head 和两个整数 leftright ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if left == right:
return head

fake_head = ListNode(next=head)
fake_head.next = head
node = fake_head

for step in range(left-1):
node = node.next

left_node = node
node = node.next
rev_left_node = node

last_node = node
cur_node = node.next

for index in range(right - left):
next_node = cur_node.next
cur_node.next = last_node
last_node = cur_node
cur_node = next_node

rev_left_node.next = cur_node
left_node.next = last_node
return fake_head.next

参考资料



文章链接:
https://www.zywvvd.com/notes/study/algorithm/list/about-list/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

算法学习笔记 —— 链表
https://www.zywvvd.com/notes/study/algorithm/list/about-list/
作者
Yiwei Zhang
发布于
2020年5月21日
许可协议