Python力扣刷题04-两两交换&.删除链表节点&链表相交&环形链表

﹏ヽ暗。殇╰゛Y 2023-09-28 23:21 61阅读 0赞

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

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

案例：

![在这里插入图片描述][0f84a6b55a874fe2851d6778123d7914.png]

输入：head = [1,2,3,4]
    输出：[2,1,4,3]

思路：

链表至少需要两个节点才能交换，这里采用递归方式实现两两交换，终止条件为链表没有节点或链表只有一个节点

首先设置两个节点，用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

原链表：1 --> 2 --> 3 --> 4    
    即：   head --> newHead.next -->
    
    新链表：2 --> 1 --> 4 --> 3   
    即：   newHead -->

实现:

class Solution:
        def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
            if not head or not head.next:
                return head #3.head:[3]
            newHead = head.next #1.newHead: [2,3,4]->[4]
            head.next = self.swapPairs(newHead.next) #2.head: [3,4]->null
    
            newHead.next = head #4.newHead:[4]->[4,3]
            return newHead

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

题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

题目描述:给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。

案例:

输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]

思路：用双指针方法，指定两个指针fast,slow初始为虚拟头节点，fast先走n+1，然后slow随着一起移动，当fast指向末尾的时候，删除掉slow所指向的节点

实现:

class Solution:
        def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
            head_dummy = ListNode()
            head_dummy.next = head
    
            slow,fast = head_dummy,head_dummy
            while(n!=0):
                #fanst向前走n步
                fast = fast.next
                n -= 1
            while(fast.next!=None):
                slow = slow.next
                fast = fast.next
            #fast走到结尾后，slow的下一个节点为倒数N个节点
            slow.next = slow.next.next #删除
            return head_dummy.next

### 面试题 02.07. 链表相交 ###

题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

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

案例:

![在这里插入图片描述][a9c74c7fa8714296a02bd7604098c73c.png]

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
    输出：Intersected at '8'
    解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
    从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
    在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

实现:

class Solution:
        def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
            """
            根据快慢法则，走的快的一定会追上走得慢的。
            在这道题里，有的链表短，他走完了就去走另一条链表，我们可以理解为走的快的指针。
    
            那么，只要其中一个链表走完了，就去走另一条链表的路。如果有交点，他们最终一定会在同一个
            位置相遇
            """
            if headA is None or headB is None:
                return None
            # 设置两个指针代替A和B
            cur_a,cur_b = headA,headB
    
            while cur_a != cur_b:
                cur_a = cur_a.next if cur_a else headB #如果a走完，切换为b走
                cur_b = cur_b.next if cur_b else headA #如果b走完，切换为a走
    
            return cur_a

### 142.环形链表 II ###

题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/

题目描述:给定一个链表的头节点 `head` ，返回链表开始入环的第一个节点。 *如果链表无环，则返回 `null`。*

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

**不允许修改** 链表。

案例:

![在这里插入图片描述][1fccd2ec822e43bc8bf500224da5cfa8.png]

输入：head = [3,2,0,-4], pos = 1
    输出：返回索引为 1 的链表节点
    解释：链表中有一个环，其尾部连接到第二个节点。

思路：这里参考代码随想录的思路

https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html\#\_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii

主要考察两知识点：

*  判断链表是否环
 *  如果有环，如何找到这个环的入口

1.判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点：**fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。**

![在这里插入图片描述][de7e302aa0a44119bfca20021f6b1fb3.gif]

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

**此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。**

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：  
![在这里插入图片描述][c6d6d4acb45344a0865a712b9ffc4f5a.png]

那么相遇时：

slow指针走过的节点数为: slow = x + y
     fast指针走过的节点数：fast = x + y + n*(y + z) #n为fast指针在环内走了n圈才遇到slow指针
     slow移动1个节点，slow移动2个节点，故fast = slow * 2 = (x+y) *2
     即(x+y)*2 = (x+y)+n*(y+z) 
     左右两边消除1个x+y,得x+y = n*(y+z)
     因为要找环形的入口，那么要求的是x，那么x=n*(y+z)-y
     再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：`x = (n - 1) (y + z) + z`，这里n>=1
     当n=1,x=z,意味着从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。  
![请添加图片描述][28368de9c04144579edd51fb955c28bc.gif]

实现:

class Solution:
        def detectCycle(self, head: ListNode) -> ListNode:
            slow, fast = head, head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                # 如果相遇
                if slow == fast:
                    p = head
                    q = slow
                    while p!=q:
                        p = p.next
                        q = q.next
                    #你也可以return q
                    return p
    
            return None

[0f84a6b55a874fe2851d6778123d7914.png]: https://img-blog.csdnimg.cn/0f84a6b55a874fe2851d6778123d7914.png
[a9c74c7fa8714296a02bd7604098c73c.png]: https://img-blog.csdnimg.cn/a9c74c7fa8714296a02bd7604098c73c.png
[1fccd2ec822e43bc8bf500224da5cfa8.png]: https://img-blog.csdnimg.cn/1fccd2ec822e43bc8bf500224da5cfa8.png
[de7e302aa0a44119bfca20021f6b1fb3.gif]: https://img-blog.csdnimg.cn/de7e302aa0a44119bfca20021f6b1fb3.gif
[c6d6d4acb45344a0865a712b9ffc4f5a.png]: https://img-blog.csdnimg.cn/c6d6d4acb45344a0865a712b9ffc4f5a.png
[28368de9c04144579edd51fb955c28bc.gif]: https://img-blog.csdnimg.cn/28368de9c04144579edd51fb955c28bc.gif