我经常搞混的点:
1. first = first.next
表示的是移动first指针的位置。
如果写first.next = first.next.next
,则表示的是更改链表结构,这会跳过first指针的下一个节点,改变链表本身的结构。
因此我区分清楚:仅仅需要移动first指针的位置,需要更改链表的结构。
2. while first:
和while first.next:
都是判断条件,两者有不同的含义。
while first:
:判断的是first指针是否存在。只要first指针指向的节点(包括最后的None)存在,循环就会继续。
while first.next:
:判断的是first指针的下一个节点是否存在。只有当first指针的下一个节点存在,循环才会继续。
24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:输入:head = []
输出:[]
示例 3:输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
奇数节点最后一个节点无法两两配对,因此最后一个节点不做交换。
偶数节点两两进行交换。
仍然使用虚拟头节点的方法。定义一个dummy节点指向head,除此之外定义一个curr临时指针用于遍历整个链表。
重点:当前节点n对应的应该是curr.next, n节点的前一个节点为curr, n节点的下一个节点为curr.next.next。
# 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 swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next is not None and curr.next.next is not None:
temp1 = curr.next # node1 temp
temp2 = curr.next.next # node2 temp
temp3 = curr.next.next.next # node3 temp
curr.next = temp2 # curr points to 2
temp2.next = temp1 # 2 points to 1
temp1.next = temp3 # 1 points to 3
curr = curr.next.next # move curr to the node before next pair
return dummy.next # dummy.next指向的是新链表的头节点
19. 删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:输入:head = [1], n = 1
输出:[]
示例 3:输入:head = [1,2], n = 1
输出:[1]
提示:
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
进阶:你能尝试使用一趟扫描实现吗?
这道题的难点是找到倒数第n个节点,让后才能删除。
这道题需要用双指针的思路,定义一个快指针,再定义一个慢指针,先让快指针走n个节点,再让两个指针同时前进,直到快指针移动到null值,这个时候慢指针对应的就是将要移除的倒数第n个节点。
首先,初始化两个指针,一开始都指向头结点。然后,让第一个指针向前移动n个节点,然后两个指针同时向前移动,直到第一个指针到达末尾。此时,第二个指针所在的位置就是倒数第n个节点。在实现过程中,为了方便处理边界条件(例如删除的节点是头结点),通常会使用一个虚拟头结点。
为什么这道题可以联想到双指针解法?双指针法在解决链表问题上非常常见,尤其是涉及链表中相对位置或者需要遍历链表找到特定元素的情况。 当你需要在链表中找到某种相对位置(如中点,倒数第N个节点等)时,你可以尝试使用双指针法。在这个具体问题中,我们知道我们需要找到倒数第n个节点,这就是一个明显的相对位置问题,因此双指针法成为一个可能的解决方案。
这里比较需要重视的一点是,先让快指针走n个节点,再让两个指针同时前进,直到快指针移动到null值,这个时候慢指针对应的就是将要移除的倒数第n个节点。但是我们要删除倒数第n个节点,需要获取的是第n个节点的前一位置的curr,因此我们可以让快指针走n+1步。
# 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 removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
time: O(n) 只遍历了一次链表。
space: O(1) 我们只使用了两个指针fast和slow,和一个虚拟节点 dummy,它们都是常数级别的空间
"""
# 创建一个虚拟节点,并将其下一个指针设置为链表的头部
dummy = ListNode(0)
dummy.next = head
# 创建两个指针,慢指针和快指针,并将它们初始化为虚拟节点
fast = dummy
slow = dummy
# 快指针比慢指针快 n+1 步
for i in range(n+1):
fast = fast.next
# 移动两个指针,直到快速指针到达链表的末尾
while fast:
fast = fast.next
slow = slow.next
# 通过更新第 (n-1) 个节点的 next 指针删除第 n 个节点
slow.next = slow.next.next
return dummy.next
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。
提示:
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点,intersectVal 为 0
如果 listA 和 listB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶:你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?
这道题需要注意的是:数值相同,不代表指针相同。
这道题目,不仅考察对链表的操作,而且还需要一些数学运算。
主要考察两知识点:
- 判断链表是否环
- 如果有环,如何找到这个环的入口
判断链表是否有环:
可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。
为什么fast 走两个节点,slow走一个节点,有环的话,一定会在环内相遇呢,而不是永远的错开呢
首先第一点:fast指针一定先进入环中,如果fast指针和slow指针相遇的话,一定是在环中相遇,这是毋庸置疑的。
题目思路:这道题目可以使用双指针法求解。大致的思路是首先通过两次遍历得到两个链表的长度,然后计算出两个链表的长度差值。然后在较长的链表上先行走这个差值的步数,然后两个指针再同时遍历,如果有相交的节点,那么最终两个指针一定会在相交节点处相遇。如果没有相交的节点,那么两个指针会同时到达链表的末尾。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
time: O(n+m) 其中n和m分别是两个链表的长度。
space: O(1)
"""
if headA is None or headB is None:
return None
lenA, lenB = 0, 0
nodeA, nodeB = headA, headB
# 计算链表A的长度
while nodeA:
lenA += 1
nodeA = nodeA.next
# 计算链表B的长度
while nodeB:
lenB += 1
nodeB = nodeB.next
nodeA, nodeB = headA, headB
# 如果链表A长于链表B,则先在链表A上走lenA - lenB步
if lenA > lenB:
for i in range(lenA - lenB):
nodeA = nodeA.next
# 如果链表B长于链表A,则先在链表B上走lenB - lenA步
elif lenB > lenA:
for i in range(lenB - lenA):
nodeB = nodeB.next
# 两个指针同时走,如果存在相交节点,那么两个指针一定会在相交节点处相遇
while nodeA != nodeB:
nodeA = nodeA.next
nodeB = nodeB.next
return nodeA
142. 环形链表 II
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
提示:
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶:你是否可以使用 O(1) 空间解决此题?
这道题分两点:
1. 找到是否有环 2.如果有环,找到环的入口
这道题的解题思路为:
使用双指针,一个快指针(每次移动两个节点)和一个慢指针(每次移动一个节点)。如果链表中有环,那么这两个指针一定会在环中的某个位置相遇。
在这两个指针相遇后,我们将快指针重置到链表的头部,并将快慢指针的移动速度都设为一次一个节点,然后继续移动,当它们再次相遇时,相遇的位置就是环的入口。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
time: O(n)
space: O(1)
"""
# 找链表中环的入口。需要确保链表至少有两个节点,这样才可能存在一个环。
# 如果链表中只有一个节点(或者没有节点),那么就不存在环,我们就可以直接返回 None。
if head is None or head.next is None:
return None
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# If there is a cycle, the slow and fast pointers will eventually meet
if (fast == slow):
# Move one of the pointers back to the start of the list
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
# If there is no cycle, return None
return None
-
定义两个指针:
fast
和slow
,分别初始化为链表的头部。 -
在一个循环中,移动
fast
指针两步,slow
指针一步。如果链表中存在环,那么这两个指针最终会在环中的某个位置相遇。 -
当发现
fast
和slow
相遇时,将fast
指针重新设置为链表的头部,并开始以同样的速度移动fast
和slow
。文章来源:https://www.toymoban.com/news/detail-552838.html -
当
fast
和slow
再次相遇时,它们会在环的入口相遇。这时返回fast
或slow
都可以,因为它们都指向环的入口。文章来源地址https://www.toymoban.com/news/detail-552838.html
到了这里,关于Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!