leetcode解题思想--206. 反转链表(Reverse Linked List)

问题描述

反转一个单链表。

示例:

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

leetcode原题链接

问题分析

此题在面试中非常常见，乍一看很简单，但是做到一次性bug free也不容易。容易出错的点如下：

此题看起来简单，解题者轻敌。
节点指针翻转时，前驱节点、后继节点容易丢失。
多个节点，需要循环，循环如何开始，如何结束，循环边界易出错。

解题思路

问题拆解是解决问题的一个非常重要的原则。此题的拆解如下：

拿到一个节点，将此节点的next指针指向此节点的前驱。

当前节点next指针指向的是后继节点，只根据当前节点无法获得前驱节点，需要一个临时变量pre_node保存前驱节点。
当前节点的next指针指向前驱节点后，后继节点就丢失了，需要一个临时变量next_node来保存后继节点。
循环处理每个节点。

循环的开始是将链表头节点作为当前节点。
循环的流转是翻转完当前节点后，将当前节点保存到pre_node，当前节点更新为next_node。
循环的结束是拿到的当前节点为空节点。

代码示例1 （python 轮回版）

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur_node = head
        pre_node = None
        while cur_node != None:
            # 处理过程中，每一行等号的右值都是下一行等号的左值，有一种轮回的美感。。
            next_node = cur_node.next
            cur_node.next = pre_node
            pre_node = cur_node
            cur_node = next_node
        return pre_node

代码示例2 （python 极简版）

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur_node, pre_node = head, None
        while cur_node != None:
            cur_node.next, pre_node, cur_node = pre_node, cur_node, cur_node.next
        return pre_node

思想总结

不要轻敌
问题拆解