您现在的位置是：首页 >学无止境 >代码随想录算法训练营第四天|LeetCode 24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07.链表相交、142.环形链表|| 网站首页学无止境

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

文档讲解：代码随想录

视频讲解：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili

状态：之前做过一次，先尝试着想了一下，然后看了一下之前的递归解法。

递归法，没有用到虚拟头节点：

• 时间复杂度：O(n)   n是链表的长度

• 空间复杂度：O(n)   每一次递归调用都会在调用栈上占用一个空间，由于递归每次处理两个节点，因此递归调用的深度是链表长度的一半，即 n/2。因此，递归调用的栈空间占用是 O(n / 2)，简化为 O(n)。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        # 待翻转的两个node分别是one和two
        one = head
        two = one.next
        three = two.next

        two.next = one
        one.next = self.swapPairs(three) # 将以three为head的后续链表两两交换，one.next应该是下一组两两交换好的第一个节点

        return two 
        

用到虚拟头节点，迭代法：

• 时间复杂度：O(n)
• 空间复杂度：O(1) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # if not head or not head.next:
        #     return head   # 有虚拟头节点，就不用对头节点特殊处理了
        dummy_head = ListNode(next = head)
        cur = dummy_head # 知道要操作的两个节点前面的那个节点才能交换那两个节点？

        # 必须有cur的下一个和下下个才能交换，否则说明已经交换结束了
        while cur.next and cur.next.next: # 分别对应链表有偶数个和奇数个节点时;要先判断cur.next否则可能会引起空指针异常
            tmp = cur.next # 临时保存节点1
            tmp1 = cur.next.next.next # 临时保存节点3

            cur.next = cur.next.next # 交换顺序，dummy_head指向节点2
            cur.next.next = tmp # 节点2指向节点1
            tmp.next = tmp1 # 节点1指向节点3

            cur = cur.next.next # cur后移两位,准备下一轮交换

        return dummy_head.next
        

对比两种方法，可以对两种方法有更深的理解。

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

文档讲解：代码随想录

视频讲解：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili

状态：发现去年也做过，有栈和双指针两个方法，看了一遍双指针的方法，然后默写对了

双指针：

关键在于如何用双指针找到要删除的节点

• 时间复杂度：O(n)

• 空间复杂度：O(1) 

# 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]:
        # 添加一个虚拟头节点,它的next指针指向链表的头节点,这样就不用添加关于头节点的特殊判断
        # 指针指向前驱节点时,好执行删除操作,就是用.next越过要删除的节点,指向后面的
        dummy = ListNode(0,head) 
        first = head #快指针
        second = dummy #慢指针
        # 快慢指针,first比second超前n个节点（快 n+1 步）.这样当first到末尾时second恰好在要删除节点的前一个节点
        for i in range(n):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next # 删除节点
        return dummy.next # 不能return head，因为head仍然指向已删除的那个节点

面试题02.07.链表相交

文档讲解：代码随想录

状态：和160.相交链表是一样的题目吧，发现已经做过两次了。有两种解法：哈希集合、双指针；

# 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) -> ListNode:
        if not headA or not headB: # 特殊情况判断：如果其中一个链表为空，则不会相交
            return None
        a = headA
        b = headB
        while a != b:
            if not a:
                a = headB
            else:
                a = a.next # 两个指针分别向后移动，当为空时就指向另一个链表，接着向后移动
            
            if not b:
                b = headA
            else:
                b = b.next
        return a  # 如果链表相交，两个指针最终走过的路程都是a_单独+ab_公共+b_单独的部分，是相等的，所以最终会同时指向交点；
# 如果链表不相交，两个指针同样会将两个链表走完然后都指向空即None；所以直接返回a即可
        

# 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) -> ListNode:
        if not headA or not headB:
            return None
        lenA = 0 # 求长度
        lenB = 0
        cur = headA
        while cur:
            cur = cur.next
            lenA += 1
        cur = headB
        while cur:
            cur = cur.next
            lenB += 1
        
        curA, curB = headA, headB
        if lenB < lenA:
            curA, curB = headB, headA
            lenA, lenB = lenB, lenA   # 让较长的链表当B,后面的情况就不用分类写了

        for _ in range(lenB - lenA):
            curB = curB.next   # 移动B指针，两个指针指向末尾对齐后，相同的起点位置
        while curA:
            if curA != curB:
                curA = curA.next
                curB = curB.next
            else:
                return curA  # curA == curB时，就是两个指针移动到了同一个位置即交点，直接返回
        return None   # 两个链表没有相交

142.环形链表||

文档讲解：代码随想录

视频讲解：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili

状态：之前做过一次，有哈希表、快慢指针两种方法

快慢指针：

判断链表是否有环

快指针每次走两个节点，慢指针每次走一个节点，相当于快指针每次以移动一个节点的速度靠近慢指针；快慢指针会相遇则说明存在环。

如果有环，如何找到这个环的入口

假设两指针在图中紫色圆点处相遇，那么快指针走过的路程为a+n(b+c)+b，n为绕环走的圈数，n >= 1因为肯定是快指针至少转完一圈后，在后面追慢指针，而后二者相遇；慢指针走过的路程为a+b；任意时刻，快指针走过的距离都为慢指针的 2 倍，则有等式a+n(b+c)+b = 2(a+b)，

要找环的入口，需要求a，根据等式 a = n(b+c) - b ；整理有 a  = (n-1)(b+c) + c，当n=1时，有a=c，说明一个指针在头节点，一个指针在相遇点，两个指针同时移动，会在环的入口处相遇。当n>1时，就是从相遇点出发的指针多在环中走了几圈，但总会在入环处相遇。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head,head
        while fast and fast.next: # 因为fast一次移动两步，所以需要判断fast.next
            fast = fast.next.next
            slow = slow.next 
            if fast == slow: # 说明二者相遇，存在环
                index1 = slow
                index2 = head
                while index1 != index2:
                    index1 = index1.next
                    index2 = index2.next
                return index1 # 环的入口点
        return None

总结