1. 问题描述

实现一个反转链表的函数，给定一个链表的头指针，返回反转后链表的头指针。要求：只能在原始链表上进行操作，时间复杂度为O(N)，空间复杂度为O(1)。

示例：

输入： 1 -> 2 -> 3
输出： 3 -> 2 -> 1

2. 解题思路

为了考验你的编程能力，面试官首先会让你写出链表中节点的定义，显然链表节点只有两个属性，一个是存储当前节点数值的变量，另一个是指向下一个节点的指针。因此链表节点的定义如下：

class LinkNode:
    def __init__(self, val):
        self.val = val
        self.next = None

接下来，就说下针对这个题的一些解题方法：
（1）首先，如果我们不考虑题目的要求，那么最容易想到的方法应该是：定义一个数组，然后遍历链表，将链表的每一个元素添加到数组中，最后倒序遍历该数组，生成一个新的链表。实现的代码如下所示：

def reverse(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    nums = []
    # 遍历链表元素，并存到数组
    while head:
        nums.append(head.val)
        head = head.next
    # 定义新的链表
    result = LinkNode(-1)
    temp = result
    # 倒序遍历数组，添加到结果链表
    for i in range(1, len(nums) + 1):
        temp.next = LinkNode(nums[-i])
        temp = temp.next
    return result.next

显然，这种方法包含两重循环遍历，加上使用了一个新的数组和新的链表，故其时间复杂度为O(2N)，空间复杂度也是O(2N)。
（2）接下来要说对第一种方法的改进方法，同样这里暂不考虑题目的要求，换个角度来思考，其实我们完全可以只使用一个新的链表而不使用数组。具体做法就是：每次遍历输入链表，直接将当前元素插入到新的链表的首端即可。实现的代码如下所示：

def reverse(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 边界条件，0个或1个元素
    if not head or not head.next:
        return head
    # 定义新的链表
    result = LinkNode(-1)
    temp = result
    # 遍历原链表元素
    while head:
        first = result.next
        # 插入到新链表的首端
        temp.next = head
        # 与原始的首端建立链接
        temp.next.next = first
        # 重新设置当前位置为首端
        temp = result
        head = head.next
    return result.next

此方法显然对第一种方法进行了优化，其时间复杂度为O(N)，空间复杂度为O(N)。
（3）最后当然就是根据题目要求，按部就班地在原链表上操作，具体的做法就是：定义一个为None的上一个节点，遍历原链表的过程中，将当前节点与上一个节点建立链接，然后更新上一个节点重复。比如：

输入： 1 -> 2 -> 3 -> 4
i=0: 1 <- 2 -> 3 -> 4
i=1: 1 <- 2 <- 3 -> 4
i=2: 1 <- 2 <- 3 <- 4

上面的示例看懂之后，下面直接看实现的代码：

def reverse(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 边界条件，0个或1个元素
    if not head or not head.next:
        return head
    # 上一个节点
    node = None
    # 遍历原链表元素
    while head:
        # 保存下一个节点，防止建立链接后原链表断裂
        temp = head.next
        # 与上一个节点建立链接
        head.next = node
        # 更新上一个节点
        node = head
        # 继续遍历链表
        head = temp
    return node

上面的代码只是在原链表上操作，中间使用的也只是临时变量，故完成满足题目的要求，时间复杂度为O(N)，空间复杂度为O(1)。

3. 小结

（1）首先，在做任何编程题的时候，一定一定一定要优先考虑边界条件！比如在本题中，边界条件就是原链表中没有元素或者只有一个元素。
（2）其次，一定要多刷编程题（极力推荐牛客网和力扣网这两个平台），尽量使用纯文本编辑器编写代码，以提高自我的编程能力。

...

00:00

面试中经典编程题总结之链表反转

1. 问题描述

2. 解题思路

3. 小结

...

FEATURED TAGS

FRIENDS