代码随想录训练营 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II

目录

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

题目链接：

题目描述：

思路：

代码：

总结：

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

题目链接：

题目描述：

解题思路：

暴力法：

双指针法：

代码：

暴力法：

双指针法：

总结：

面试题 02.07. 链表相交

题目链接：

题目描述：

解题思路：

暴力法：

末尾对齐法：

代码：

链表相交 142.环形链表II

题目链接：

题目描述：

解题思路：

快慢指针法：

集合法：

代码：

快慢指针法：

集合法：

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

题目链接：

24. 两两交换链表中的节点 – 力扣（LeetCode）

题目描述：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路：

1、依旧使用虚拟头节点。

2、共分三步解决

（1）将cur（虚拟头节点）指向第二个元素

（2）将第二个元素与第一个元素交换位置

（3）将第一个元素指向第三个元素

代码：

# 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]:
        dummy_head = ListNode(next = head)
        cur = dummy_head
        while cur.next != None and cur.next.next != None:
            temp1 = cur.next
            temp2 = cur.next.next.next
            cur.next = cur.next.next
            cur.next.next = temp1
            cur.next.next.next = temp2
            cur = cur.next.next
        return dummy_head.next

总结：

1、使用指针临时储存节点。

2、进行循环时，注意边界问题。

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

题目链接：

19. 删除链表的倒数第 N 个结点 – 力扣（LeetCode）

题目描述：

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

解题思路：

暴力法：

1、使用暴力法，先循环得出链表长度（size），再size – n 得出删除的节点在哪一位，后直接删除即可（但是使用两次循环，不够优雅）

双指针法：

2、双指针法，快指针先移动n+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]:
        size = 1
        dummy_head = ListNode(next = head)
        cur = dummy_head.next
        while cur.next:
            cur = cur.next
            size += 1
        true_num = size - n
        cur = dummy_head
        for _ in range(true_num):
            cur = cur.next
        cur.next = cur.next.next
        return dummy_head.next

双指针法：

# 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]:
        dummy_head = ListNode(next = head)
        fast = dummy_head
        slow = dummy_head
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next

总结：

注意边界问题，并且使用虚拟头节点（更优雅）

面试题 02.07. 链表相交

题目链接：

面试题 02.07. 链表相交 – 力扣（LeetCode）

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

解题思路：

暴力法：

每个节点均与另一个链表的所有节点对比一次，找到相同的返回节点，没有相同的返回None（非常不优雅）

末尾对齐法：

求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点，否则循环退出返回空指针。

代码：

# 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:
        curA = headA
        curB = headB
        lenA = 0
        lenB = 0
        cur = headA
        while cur:
            lenA += 1
            cur = cur.next
        cur = headB
        while cur:
            lenB += 1
            cur = cur.next
        if lenA > lenB:
            curA, curB = curB, curA
            lenA, lenB = lenB, lenA 
        for _ in range(lenB - lenA):
            curB = curB.next
        while curA:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None

链表相交 142.环形链表II

题目链接：

 142. 环形链表 II – 力扣（LeetCode）

题目描述：

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

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

不允许修改 链表。

解题思路：

快慢指针法：

共分为两步

1、判断是否有环：

        通过快慢指针，快指针比慢指针每次移动快一位，如果链表中存在环，则快指针最终会追上慢指针，然后再使用两个指针找到环的入口节点。

2、找到环的入口点：

        当快慢指针相遇时，将其中一个指针（比如慢指针）移到链表头。然后，以相同的速度移动快慢指针，直到它们再次相遇。相遇点就是环的入口节点

如果链表中不存在环，则快指针会提前到达链表末尾。

集合法：

使用python中集合的特性解决

代码：

快慢指针法：

# 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 = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None 

集合法：

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


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        
        while head:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        
        return None