LeetCode(四)反转链表

发表于 | 分类于

预备知识：Data Structure(一) Linked List
代码链接
题目题目链接

反转链表

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路一： 迭代的方式

通过遍历的方式，核心代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reverseList(_ head: ListNode?) -> ListNode? {
    
    var newNode = head
    var preNode: ListNode?
    while newNode != nil {
        
        var nextNode: ListNode?
        
        if let node = newNode {
            nextNode = node.next
            node.next = preNode
            preNode = node
        }
        newNode = nextNode
    }
    
    
    return preNode
}

思路一： 递归的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func reverseList2(_ head: ListNode?) -> ListNode? {
    
    if head?.next == nil  {
        return head
        
    }else {
        let temp = head?.next
        head?.next = nil
        let node = reverseList(temp)
        temp?.next = head
        
        return node
    }
}

结果

总结：

看这个问题的时候，对链表还不太熟悉，熟悉了之后再解决这个问题的时候发现，这个反转的过成功根本就看不到链表啊 … 有木有？题目中给出了 Node 的定义，以及 Node 中 value 的类型，其实这就够了，我第一遍做的时候，在 LeetCode 网站上把定义链表的代码也贴上了，然后还加上了 firt、last 以及 description 还有 append(） 方法，虽然正确，但是编译时不通过的，因为 LeetCode 内部已经实现了，只需要写反转算法这块代码就好了，这块儿折腾了一大会儿才反应过来。

对于思路一，迭代这种方式，在纸上画个草稿，就差不多能写出来了。
思路二，是通过递归的方式去解决这个问题的，主要是处理好结束条件

-------------本文结束谢谢欣赏-------------
Alice wechat