等长分割循环链表

[!Tip]

本节源代码见Github链接🔗


问题描述

如何把一个循环链表分割成两个长度相等的部分?如果链表的结点数是奇数,那么让第一个链表的结点数比第二个多1个。


核心思路

参考08-找到链表的中间结点,用移速不同的两个指针,找到中间结点,然后将链表分割为两个循环链表。包含以下3步:

  1. 定义两个指向头结点的指针slowPtr和fastPtr,以不同的速度向前移动指针,slowPtr每次移动一个结点,fastPtr每次移动两个结点;
  2. 当fastPtr移动到末尾时停止移动,此时slowPtr正指向中间结点;
  3. 将fastPtr的后继指针指向slowPtr的后继结点,将slowPtr的后继指针指向链表头结点。 等长分割循环链表.png

实现代码

【👉🏻>>点击展开查看代码】
        
/**  
 * 等长分割循环链表  
 *  
 * @param headNode  
 * @author: Max Solider  
 * @date: 2022/10/11 22:39  
 */
 void splitCircularList(NormalListNode headNode) {  
    if (headNode == null || headNode.getNext() == null || headNode.getNext() == headNode) {  
        System.out.println("The linked list cannot be divided into two.");  
        return;    }  
    NormalListNode slowPtr = headNode;  
    NormalListNode fastPtr = headNode;  
    while (fastPtr.getNext() != headNode && fastPtr.getNext().getNext() != headNode) {  
        slowPtr = slowPtr.getNext();  
        fastPtr = fastPtr.getNext().getNext();  
    }  
    if (fastPtr.getNext() != headNode) {  
        fastPtr = fastPtr.getNext();  
    }  
    NormalListNode aList = headNode;  
    NormalListNode bList = slowPtr.getNext();  
    slowPtr.setNext(aList);  
    fastPtr.setNext(bList);  
    listLength(aList);  
    System.out.println("========");  
    listLength(bList);  
}
        
    

时间复杂度

时间复杂度为O(n),用于遍历链表。


空间复杂度

空间复杂度为O(1),用于存储临时变量。


© MaxSolider all right reserved,powered by Gitbook文件修订时间: 2022-10-12 23:31:04

results matching ""

    No results matching ""