代码随想录算法训练营第四天 | Python | LeetCode24.两两交换链表中的节点、19.删除链表的倒数第 N 个结点、面试题02.07.链表相交、42.环形链表 II

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
文章/视频链接：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
掌握程度：3星

双指针

反转

指针移动

结束条件

注意！结束条件竟是 while cur and cur.next，两种解释：

1. 链表长度<2时，直接返回自身
2. 推演最后一步，发现有两种可能情况，剩余0/1个需要旋转的节点，这时候选择不旋转，直接返回。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = dummy = ListNode(val=0, next=head)
        cur = head
        while cur and cur.next:
            tmp = cur.next
            pre.next = tmp
            cur.next = tmp.next
            tmp.next = cur
            
            pre = cur
            cur = pre.next
        return dummy.next

迭代

1 -> 2 -> 3 -> 4 -> None

我们可以把 1 -> 2 拿出来，让 2 -> 1，1 -> 转换后的链表，做输出。后面的链表做转换也是这个流程：处理 3 -> 4，让 4 -> 3，3 -> 后面的链表做转换。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        while head == None or head.next == None:
            return head
        node1 = head
        node2 = head.next
        node3 = head.next.next
        node2.next = node1
        node1.next = self.swapPairs(node3)
        return node2

LeetCode19. 删除链表的倒数第 N 个结点

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
文章/视频链接：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
掌握程度：三星

暴力解法肯定是遍历一遍，记录链表长度，再遍历一遍，找到倒数第n个节点在哪，删除。

简单的办法是用双指针，让slow和fast中间相隔n个节点。这里仍然需要注意循环结束。无非是cur和cur.next两种常见情况，在最后一步推演一下就能得出。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = dummy = ListNode(val=0, next=head)
        for _ in range(n):
            fast = fast.next
        slow = dummy
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

面试题 02.07. 链表相交

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
文章/视频链接：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
掌握程度：2星

一开始拿到这道题的时候，想法是反转链表，判断数值是否相等。但是发现题目中写了这么一句话：注意，函数返回结果后，链表必须保持其原始结构。那反转链表是肯定不能做的了。

我会想到反转链表的原因是，想要判断数值相等。其实这有点多此一举了，当我们指针指向某个节点时，判断相等指的是指链表相等而不是数值相等。没必要依次判断数值了。

这么说就简单了，我们让链表末尾对齐，判断是否相等就好了。

常规做法

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        curA, curB = headA, headB
        sizeA, sizeB = 0, 0
        while curA:
            sizeA += 1
            curA = curA.next
        while curB:
            sizeB += 1
            curB = curB.next
        curA, curB = headA, headB
        if sizeA > sizeB:
            res = sizeA - sizeB
            for _ in range(res):
                curA = curA.next
        elif sizeA < sizeB:
            res = sizeB - sizeA
            for _ in range(res):
                curB = curB.next
        while curA:
            if curA == curB:
                return curA
            curA = curA.next
            curB = curB.next
        return None

双指针

一个没见过就想不出来的做法：
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/solutions/1190240/mian-shi-ti-0207-lian-biao-xiang-jiao-sh-b8hn/

咱们也不知道为什么但就是很厉害

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
文章/视频链接：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
掌握程度：0星

双指针

1. fast每次走两格，slow每次走一格，如果能相遇，那么是环形链表。为什么一定能相遇？快慢指针的相对速度是1格，fast一定能遇到slow。加入相对速度是2，fast可能会越过slow。
2. p从head点出发，q从相遇点出发，一定会在环点相遇。
   

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = head
        slow = head
        while True:
            if not (fast and fast.next):
                return
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

哈希表

遍历链表，保存在哈希表中，如果遇到之前见过的链表，那么返回，如果没有，返回null

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        Hash = {}
        cur = head
        while cur:
            if cur in Hash:
                return cur
            Hash[cur] = True
            cur = cur.next
        return

为什么要用哈希表保存链表，不用list？
查找快，哈希表查找时间复杂度为O(1)，而链表是O(n).

今天就到这里了，再见ヾ(￣▽￣)Bye_Bye