初级算法-链表-反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

反转链表示例.jpg

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

摘一个示例做个说明.
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

条件分析:

1. 单链表头节点 -> 需要从头节点开始反转

解决思路1:

1. 根据分析1,采用迭代方式进行反转

先定义返回的空链表和循环链表(需要反转的链表).然后当循环链表不空的时候进行循环(即链表没有到尾节点),定义临时变量为循环链表的next,然后让循环链表的next指向返回链表.返回的链表为循环链表.然后循环链表为临时链表(即下一个节点后的链表)

func reverseList(_ head: ListNode?) -> ListNode? {
    // 返回链表
    var newHead: ListNode? = nil
    // 循环节点
    var old = head
    while old != nil {
        // 先定义临时变量存储next
        let tmp = old?.next
        // 节点指向返回链表(定义新链表承接)
        old?.next = newHead
        // 返回链表等于循环链表
        newHead = old
        // 让循环链表为临时变量,进行继续循环
        old = tmp
    }
    
    return newHead
}

解决思路2:

1. 根据分析1,采用递归方式进行反转

先判断链表是否为空或者单节点链表,是则直接返回(也用以结束递归).然后开始递归节点,直到尾节点结束递归.然后从尾部开始反转链表节点.直到头节点.然后置空头节点的next即可.

func reverseList(_ head: ListNode?) -> ListNode? {
    // 单链表和空链表直接返回
    if head == nil || head?.next == nil{
        return head
    }
    // 递归调用,直到尾节点
    let node : ListNode? = reverseList(head?.next)
    // 直接反转链表节点指向
    head?.next?.next = head
    // 最后next置空
    head?.next = nil
    return node
}

测试用例:

let endNode = ListNode.init(0)
let fourNode = ListNode.init(1)
fourNode.next = endNode
let threeNode = ListNode.init(2)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(4)
firstNode.next = secondNode
let headNode = ListNode.init(5)
headNode.next = firstNode

考察要点:

• 递归
• 链表