逆置单向链表

[!Tip]

本节源代码见Github链接🔗


问题描述

逆置单向链表


核心思路

通过遍历链表,依次逆置结点的next指向来解决。主要包含以下2步:

  1. 遍历链表;
  2. 在遍历过程中,用临时指针指向下一个结点,更新当前节点的next指针信息。

实现代码

【👉🏻>>点击展开查看代码】
        
/**  
 * 逆置单向链表  
 *  
 * @param headNode  
 * @return NormalListNode  
 * @author: Max Solider  
 * @date: 2022/10/9 14:18  
 */
 NormalListNode reverseList(NormalListNode headNode) {  
    if (headNode == null || headNode.getNext() == null) {  
        return headNode;  
    }  
    NormalListNode nextNode = null;  
    NormalListNode previousNode = null;  
    while (headNode != null) {  
        nextNode = headNode.getNext();  
        headNode.setNext(previousNode);  
        previousNode = headNode;  
        headNode = nextNode;  
    }  
    headNode = previousNode;  
    return headNode;  
}
        
    

时间复杂度

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


空间复杂度

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


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

results matching ""

    No results matching ""