算法:单链表反转


本篇使用PowerShell语法演示单链表的反转

思路:
1.从第二个结点开始,把后一个结点的指针指向前一个结点
2.第一个结点的Next节点要置空,否则会出现环。

具体如下图

Class LinkedNode {
[LinkedNode]$Next;
[Object]$Value;
}

#
# 遍历链表
#
function Foreach-Node
{
    param([LinkedNode]$Node)

    while($Node -ne $null){
        $Node
        $Node=$Node.Next
    }
}

#
# 打印链表
#
function Print-Node
{
    param([LinkedNode]$Node)

    $values = Foreach-Node -Node $Node | Select -ExpandProperty Value
    Write-Host ($values -join ',')
}

#
# 将数组转换成链表
#
function ConvertFrom-Array
{
    param($Array)
    if(($Array -eq $null) -or ($Array.length -eq 0))
    {
        return $null
    }
    $header = [LinkedNode]::new()
    $header.Value = $Array[0]
    $node = $header
    for ($i = 1; $i -lt $Array.length; $i++)
    { 
        $node.Next = [LinkedNode]::new()
        $node.Next.Value = $Array[$i]
        $node = $node.Next
    }
    return $header
}

#
# 反转链表
#
function Reverse-Node
{
    param([LinkedNode]$Node)
    if(($Node -eq $null) -or ($Node.Next -eq $null)){
        return $Node
    }

    [LinkedNode]$pre=$Node
    [LinkedNode]$current = $Node.Next

    $pre.Next = $null
    while($current -ne $null){
        $temp = $current.Next
        
        $current.Next = $pre
        $pre = $current
        $current = $temp
    }
    return $pre
}


#
# 测试
#
Write-Host "原链表:"
$node = ConvertFrom-Array @(1..10)
Print-Node -Node $node
Write-Host "反转后:"
$newNode = Reverse-Node -Node $node
Print-Node -Node $newNode

测试输出

原链表:
1,2,3,4,5,6,7,8,9,10
反转后:
10,9,8,7,6,5,4,3,2,1
本文链接: https://www.pstips.net/reverse-linkednode.html
请尊重原作者和编辑的辛勤劳动,欢迎转载,并注明出处!

关于 Mooser Lee

我是一个Powershell的爱好者,创建了PowerShell中文博客,热衷于Powershell技术的搜集和分享。本站部分内容来源于互联网,不足之处敬请谅解,并欢迎您批评指正。

发表评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注