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

目录

• 链表
• 算法详解
• • 24. 两两交换链表中的节点
  • • (1) 易错点
    • (2) 思路
    • (3) 代码
  • 19.删除链表的倒数第N个节点
  • • (1) 易错点
    • (2) 思路
    • (3) 代码
  • 面试题 02.07. 链表相交
  • • (1) 易错点
    • (2) 思路
    • (3) 代码
  • 142.环形链表II
  • • (1) 关键点
    • (2) 思路
    • (3) 代码
• 参考资料

链表

链表：地址非连续，靠指针相互联系。

注意：具体的地址分散情况依据设定不同。

算法详解

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

(1) 易错点

1. 虚拟头结点使用：由于头结点并没有真正的前置节点，交换时假设不采用虚拟头结点则需要对头结点单独处理。
2. 两个节点交换涉及到四个节点：在交换A-B这段链表切片上，实现AB的交换，还涉及到A的前置节点和B的后置节点。
3. 循环条件：当cur执行到cur.next.nexr=None时，达到链表尾部，此时跳出循环，另外，假设cur.next已经为None，则无法执行cur.next.next，故需添加cur.next的条件。

(2) 思路

为不单独处理头结点的交换，创建虚拟头结点指向head。如上文所说，AB的交换涉及到四个节点，A节点可以用指pre针访问，而A的前置节点无法访问；B节点用pre.next访问，而当交换发生时，B指向A，B节点原本的后置节点无法访问，因此我们需要一个指针cur来访问A的前置节点，而指针tail访问B的后置节点。

• 创建虚拟头结点dummy_head，cur指向dummy_head。
• 初始化pre和tail的位置。
• 交换：①将A的前置节点指向B；②将B指向A；③将A指向B的后置节点。如下图所示：

  

(3) 代码

class Solution:    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:        dummy_head = ListNode(next=head)        cur = dummy_head        # 当cur.next.next.next == None 时，到链表尾部        while cur.next and cur.next.next:            pre = cur.next            tail = cur.next.next.next            cur.next = cur.next.next            cur.next.next = pre            pre.next = tail            # 相邻两个元素交换，因此指针移动两位            cur = cur.next.next        return dummy_head.next

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

(1) 易错点

1. 循环条件：当tail.next为None时，代表tail节点到链表结尾，此时跳出循环。
2. 单链表无法反向访问：和删除链表的第n个元素类似，一开始思考可以先遍历到链表尾部然后反向找第n个节点，然而单链表无法反向访问，故行不通。

(2) 思路

设置两个间隔为n的指针从head遍历到链表尾，此时前一个指针所指的位置就是待删除的节点。

• 设置tail节点走到第n个节点；
• cur从head出发，tail从第n个节点出发遍历；
• 当tail访问到链表尾节点时跳出循环；
• 删除cur.next元素。
• 具体思路如下图所示：

  

(3) 代码

class Solution:    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:        # 创建虚拟头结点避免删除头结点时要另外执行        dummy_head = ListNode(next=head)        cur = dummy_head        tail = dummy_head        # 在cur和tail之间创建间隔n        for _ in range(n):            tail = tail.next        # 将tail移动至链表尾部此时cur.next即为待删除元素        while tail.next:            cur = cur.next            tail = tail.next                cur.next = cur.next.next        return dummy_head.next

面试题 02.07. 链表相交

(1) 易错点

1. 相交比较的是指针不是节点值。
2. 尾部对齐之后较长的链表应该从链表长度之差处开始遍历并比较。

(2) 思路

将两条链表尾部对齐之后，假设有相交，则从尾节点往head方向会出现相等的节点。

• 分别遍历链表A和B得到长度lenA和LenB;
• 为简化，设置链表A为较长的一条，若不满足则lenA、lenB和curA、curB交换；
• 计算长度差lenAa-lenB，将curA遍历到和curB对齐；
• 同时移动curA和curB直至相等，此时找到链表交点；
• 若遍历到链表尾部也不相等则链表不相交。
• 具体思路如下图所示：

  

(3) 代码

class Solution:    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:        cur_a, len_a = headA, 0        cur_b, len_b = headB, 0        # 将a和b都先移动到链表尾部得到链表长度        while cur_a:            cur_a = cur_a.next            len_a += 1        while cur_b:            cur_b = cur_b.next            len_b += 1                # 始终让cur_a指向较长的链表        cur_a, cur_b = headA, headB        if len_b > len_a:            cur_a, cur_b = cur_b, cur_a            len_a, len_b = len_b, len_a                        # 计算两条链之间的长度差        len_ab = len_a -len_b        # 将两条链表尾部对齐        for _ in range(len_ab):            cur_a = cur_a.next                # 将两条链同时移动并比较指针        while cur_a and cur_b:            if cur_a == cur_b:                return cur_a            cur_a = cur_a.next            cur_b = cur_b.next                return None

142.环形链表II

(1) 关键点

1. 链表是否有环判断：若slow和fast相遇则链表有环；
2. slow和fast相遇点计算。

   注意：至少一圈内slow和fast会相遇。

(2) 思路

当链表中存在环时，每次移动一个节点的slow指针和每次移动两个节点的fast指针会在环中相遇。通过简单的数学计算（如图）发现，当slow和fast相遇时，此时fast位置不变，节点slow从head和fast一起同时移动，且每次只移动一个节点，当slow和fast再次相遇时为环的入口。

• 初始化slow、fast并移动，slow每次移动一个节点，fast移动两个节点；
• 第一次相遇：fast首先进入环，移动一段时间后和后进入环的slow相遇，即为图中绿色节点；
• 第二次相遇：fast从第一次相遇点出发，slow从head出发，每次均只移动一个节点；当第二次相遇时为环入口，即图中黄色节点。

  !

(3) 代码

class Solution:    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:        slow, fast = head, head        while fast and fast.next:            slow = slow.next            fast = fast.next.next                        if slow == fast:                slow = head                while not(slow == fast):                    slow = slow.next                    fast = fast.next                return slow        return None

参考资料

（1）24. 两两交换链表中的节点

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

（3）面试题 02.07. 链表相交

（4） 142.环形链表II