Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II

这篇具有很好参考价值的文章主要介绍了Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

我经常搞混的点:

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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构


输入: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。

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

# 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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构


输入: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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入: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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入: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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入: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:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
 

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
 

进阶:你是否可以使用 O(1) 空间解决此题?

这道题分两点:

1. 找到是否有环  2.如果有环,找到环的入口

这道题的解题思路为:

使用双指针,一个快指针(每次移动两个节点)和一个慢指针(每次移动一个节点)。如果链表中有环,那么这两个指针一定会在环中的某个位置相遇。

在这两个指针相遇后,我们将快指针重置到链表的头部,并将快慢指针的移动速度都设为一次一个节点,然后继续移动,当它们再次相遇时,相遇的位置就是环的入口。

Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II,Leetcode刷题记录,链表,数据结构

# 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
                 
  1. 定义两个指针:fastslow,分别初始化为链表的头部。

  2. 在一个循环中,移动fast指针两步,slow指针一步。如果链表中存在环,那么这两个指针最终会在环中的某个位置相遇。

  3. 当发现fastslow相遇时,将fast指针重新设置为链表的头部,并开始以同样的速度移动fastslow

  4. fastslow再次相遇时,它们会在环的入口相遇。这时返回fastslow都可以,因为它们都指向环的入口。文章来源地址https://www.toymoban.com/news/detail-552838.html

到了这里,关于Day 4 链表: 24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点, 面试题 02.07. 链表相交 ,142.环形链表II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包