LeetCode—链表反转

大家好，欢迎来到IT知识分享网。

题目来源于 LeetCode 的第 206 题，难度为：easy。目前的通过率是71.7%。

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

题目解析

设置三个节点pre、cur、next

• （1）每次查看cur节点是否为NULL，如果是，则结束循环，获得结果
• （2）如果cur节点不是为NULL，则先设置临时变量next为cur的下一个节点
• （3）让cur的下一个节点变成指向pre，而后pre移动cur，cur移动到next
• （4）重复（1）（2）（3）

动画演示

为了让动画看的简单易懂，next 指针就没有画， next = cur?.next

代码实现

/ * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val = 0; self.next = nil; } * public init(_ val: Int) { self.val = val; self.next = nil; } * public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; } * } */ class Solution { func reverseList(_ head: ListNode?) -> ListNode? { var cur = head var next = cur?.next var pre : ListNode? while (cur != nil) { next = cur?.next cur?.next = pre pre = cur cur = next } return pre } }

进阶解法：递归实现

可以查看前期分享的文章 LeetCode 递归编程技巧-链表算法题 来获得答案。