链表基础#

1
class Solution:
2
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        dummy = ListNode(next = head)
4
        cur = dummy
5
        # 由于是两两交换，所以需要至少两个节点才能进行交换
6
        # 当 cur.next 和 cur.next.next 都存在时，才进行交换
7
        while cur.next and cur.next.next:
8
            # temp1 => 准备交换的第一个节点
9
            temp1 = cur.next
10
            # temp1 => temp1.next => temp2
11
            temp2 = cur.next.next.next
12
            cur.next = temp1.next
13
            temp1.next.next = temp1
14
            temp1.next = temp2
15
            cur = temp1
16
        return dummy.next

1
class Solution:
2
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
3
        dummy = ListNode(next=head)
4
        fast = slow = dummy
5
        # fast 先走 n+1 步，这样 fast 和 slow 之间的距离为 n
6
        for _ in range(n + 1):
7
            fast = fast.next
8

9
        # 当 fast 到达链表末尾时，slow 的下一个节点就是要删除的节点
10
        while fast:
11
            fast = fast.next
12
            slow = slow.next
13

14
        # 删除节点
15
        slow.next = slow.next.next
16
        return dummy.next

1
class Solution:
2
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
3
        l1, l2 = headA, headB
4
        # 当 l1 和 l2 相等时，有两种情况：1. 相交节点；2. 都为 None
5
        while l1 != l2:
6
            if not l1:
7
                l1 = headB
8
            else:
9
                l1 = l1.next
10
            if not l2:
11
                l2 = headA
12
            else:
13
                l2 = l2.next
14
        # 返回相交节点或 None
15
        return l1

1
class Solution:
2
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        fast, slow = head, head
4
        # 当快指针为None 或者快指针的下一个节点为 None 时，说明链表没有环
5
        while fast and fast.next:
6
            fast = fast.next.next
7
            slow = slow.next
8
            # 当快慢指针相遇时，说明链表有环，接下来就需要找到环的入口节点
9
            if fast == slow:
10
                fast = head
11
                # 当第二次快慢指针相遇时，slow 就是环的入口节点
12
                while fast != slow:
13
                    fast = fast.next
14
                    slow = slow.next
15
                return slow
16
        return None