【Swift写算法】链表的反转

本文介绍: 假设我们正在开发一款小游戏，在游戏中存在这样一种场景，当队伍排名最后一名玩家在捡到某种道具后，可以使用该道具对他所在的队伍进行一个反转，比如1-2-3-4-5分别是五名玩家，反转后变成5-4-3-2-1，请问如何在链表的场景下进行反转？的解决办法，递归算法的核心逻辑在于先递归遍历出最后一个链表节点，然后以相反的方向将前一个元素赋值给后一个元素的next，递归结束刚好完成从后向前的递归反转，具体代码如下。关于这个问题有多种解法，我们在这里介绍两种解法。首先我们准备好基本的链表代码，如下。

假设我们正在开发一款小游戏，在游戏中存在这样一种场景，当队伍排名最后一名玩家在捡到某种道具后，可以使用该道具对他所在的队伍进行一个反转，比如1-2-3-4-5分别是五名玩家，反转后变成5-4-3-2-1，请问如何在链表的场景下进行反转？

关于这个问题有多种解法，我们在这里介绍两种解法。一是递归解法，二是进出栈解法。

首先我们准备好基本的链表代码，如下。

//设计一个简单的链表节点类型
class LinkedListNode {
    var content: String
    var next: LinkedListNode?
    
    init(content: String, next: LinkedListNode? = nil) {
        self.content = content
        self.next = next
    }
}

//创建链表并完成初始化
func getLinkedList() -&gt; LinkedListNode {
    var p4 = LinkedListNode(content: "I am p4", next: nil)
    var p3 = LinkedListNode(content: "I am p3", next: p4)
    var p2 = LinkedListNode(content: "I am p2", next: p3)
    var p1 = LinkedListNode(content: "I am p1", next: p2)
    var head = LinkedListNode(content: "I am head", next: p1)
    
    return head
}

在准备好一个链表输出方法

//输出链表
func printLinkedList(linkedList: LinkedListNode) {
    var p: LinkedListNode? = linkedList
    
    while true {
        guard p == nil else {
            print(p!.content)
            continue
        }
        break
    }
}

现在我们开始进行递归算法的解决办法，递归算法的核心逻辑在于先递归遍历出最后一个链表节点，然后以相反的方向将前一个元素赋值给后一个元素的next，递归结束刚好完成从后向前的递归反转，具体代码如下。

//递归版
func reverseLinkedList(linkedList: LinkedListNode) -&gt; LinkedListNode {
    //确定是否是链表的最后一个节点
    if linkedList.next == nil {
        return linkedList
    }
    
    //获取到最后一个节点tail
    let tail = reverseLinkedList(linkedList: linkedList.next!)
    //在每一次递归中对next进行反转
    linkedList.next?.next = linkedList
    linkedList.next = nil
    //返回tail的指针，现在它是反转后的head节点了
    return tail
}

当然我们也可以采取另一种方式来反转链表，该方法非常简单，甚至可以在此基础上做更多的改造，这个方法的核心逻辑就是用一个容器来辅助反转。

//进出栈版
func reverseLinkedList(linkedList: LinkedListNode) -&gt; LinkedListNode {
    var p: LinkedListNode? = linkedList
        
    //建立一个数组
    var nodeArray: Array<LinkedListNode&gt; = []
    
    while true {
        guard p == nil else {
            nodeArray.insert(p!, at: 0)
            p = p!.next
            continue
        }
        break
    }
    
    for i in nodeArray.indices {
        if i == nodeArray.count - 1 {
            nodeArray[i].next = nil
        } else {
            nodeArray[i].next = nodeArray[i + 1]
        }
    }
    
    return nodeArray[0]
}