代码随想录算法训练营第四天|LC24.两两交换链表中的节点|LC19. 删除链表的倒数第 N 个结点|LC160. 相交链表|142. 环形链表 II

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

        1、需要一个虚拟节点进行帮助；

        2、注意虚拟节点的连接以及变化（尝试有点困惑它的变化，后面有点理解）；

        3、注意后续第二组的交换时如何与第一组交换进行连接；

from typing import Optional


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 head is None or head.next is None:
            return head
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next and cur.next.next:
            tmp1 = cur.next
            tmp2 = cur.next.next.next

            cur.next = cur.next.next # 先把虚拟节点与改变后的头节点进行连接
            cur.next.next = tmp1 # 节点2指向节点1
            tmp1.next = tmp2
            cur = cur.next.next # 将指针（虚拟头节点）进行改变，去进行后续的两两交换
        return dummy_head.next


if __name__ == '__main__':
    head = ListNode(None)
    cur = head
    for i in [1, 2, 3, 4, 5, 6]:  # 逐个生成节点
        cur.next = ListNode(i)
        cur = cur.next
    res = Solution().swapPairs(head.next)
    while res:
        print(res.val, end=' ')
        res = res.next

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

        1、注意n+1，指针移动到最后是可以移动到末尾节点的next节点；

from typing import Optional


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
        # 目的在于让fast和slow同时移动
        # 为什么n+1，因为最后fast可以指向最后一个节点的next;
        for i in range(n+1):
            fast = fast.next
        # fast和slow同时移动，并指向末尾
        while fast:
            fast = fast.next
            slow = slow.next
        # 以slow指针指向目标删除元素的前一个节点，并进行连接
        slow.next = slow.next.next
        return dummy_head.next


if __name__ == '__main__':
    head = ListNode(None)
    cur = head
    for i in [1, 2, 3, 4, 5]:  # 逐个生成节点
        cur.next = ListNode(i)
        cur = cur.next
    n = 2
    res = Solution().removeNthFromEnd(head.next, n)
    while res:
        print(res.val, end=' ')
        res = res.next

lc - 力扣（LeetCode）

        1、相交：即交点后所有节点的值都一样；

        2、末尾长度一致，即可以从末尾开始（末尾对齐后操作）；

from typing import Optional


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 求长度
        lenA, lenB = 0, 0
        cur = headA
        while cur:
            cur = cur.next
            lenA += 1
        cur = headB
        while cur:
            cur = cur.next
            lenB += 1
        curA, curB = headA, headB
        # 交换长度，让curB成为长的那个链表（好看，好理解）
        if lenA > lenB:
            lenA, lenB = lenB, lenA
            curA, curB = curB, curA
        # 让curB指针和curA指针在同一位置（末尾对其）
        for _ in range(lenB-lenA):
            curB = curB.next
        while curA:
            if curA == curB:
                return curA
            # 在pycharm中，需要这样以下写法
            # if curA.val == curB.val:
                # return curA.val
            else:
                curA = curA.next
                curB = curB.next
        return None


if __name__ == '__main__':
    headA = ListNode(None)
    curA = headA
    for i in [0, 9, 1, 2, 4]:
        curA.next = ListNode(i)
        curA = curA.next
    headB = ListNode(None)
    curB = headB
    for i in [1, 2, 4]:
        curB.next = ListNode(i)
        curB = curB.next
    res = Solution().getIntersectionNode(headA.next, headB.next)
    print(res)
    # while res:
        # print(res.val, end=' ')
        # res = res.next

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

难点：     

        1、判断链表是否有环；

        2、若存在环，如何找到环开始的地方（入口）；

判断是否有环：使用快慢指针法，分别定义fast和slow两个指针，fast每次移动2个节点，slow指针每次移动1个节点，若两个指针在途中相遇，说明这个链表有环；

为什么？

        1、首先，若链表中存在环，fast指针移动2个节点，故fast指针首先进入环中，如果fast和slow指针相遇的话，一定实在环中相遇；

        2、fast指针走2个节点，slow指针走一个节点，对于环来说，其实是fast指针在一个节点一个节点的犯追slow指针（靠近slow），所以，fast指针一定可以和slow重合；

若存在环，如何找到环的入口?

        从头节点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点；（也就是说，在相遇节点处，定义一个指针index1，那么在头节点处定一个指针index2，让两个指针同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。）

from typing import Optional


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 设定2个初始节点
        fast = head
        slow = head
        while fast and fast.next:
            # fast走2个节点，slow走一个节点
            fast = fast.next.next
            slow = slow.next
            # 当相遇时
            if slow == fast:
                # slow回到头节点，用来计算环的入口
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                # 相遇时即为环的入口，即slow的索引
                return slow
        return None

问题：在pycharm中没有找到对环链表的书写，没有测试案例进行debug，设计好数据后输出为0，存在一定的问题；（顶个点，后续再来解决）

链表总结

        1、虚拟头节点的重要性，对于删除节点，特别是头节点处理操作特别清晰易懂；

        2、反转列表要注意使用双指针法将头节点指向虚拟节点进行反转；

        3、相交链表要注意结尾对齐（根据特点出发理解，目标节点后所有值有一样）

        4、指针最后可以指向末尾节点的next节点；

        5、链表不想数组，没有len，计算长度只能循环一步一步自加1（+=1）才可以；

        6、环形链表要注意如何判断链表中存在环，以及环的初始点（即入口）；