图解精选 TOP 面试题 005 | 反转链表之迭代求解

江不知

发布于 2019-12-19 15:42:56

5310

发布于 2019-12-19 15:42:56

文章被收录于专栏：编程拯救世界

该系列题目取自 LeetCode 精选 TOP 面试题列表：https://leetcode-cn.com/problemset/top/

题目描述

LeetCode 206. 反转链表：https://leetcode-cn.com/problems/reverse-linked-list/

反转一个单链表。

示例:

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

进阶:

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

解题思路

链表反转在面试中非常常见，我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。

在反转的过程中：

为了反转，我们需要知道节点的上一个节点
为了继续遍历，我们也需要知道节点的下一个节点

因此，在循环迭代节点的过程中需执行如下步骤（设当前节点为 cur）：

保存节点的前一个节点 pre
保存节点的下一个节点 next
修改节点的 next 指针，使它指向前一个节点 cur.next = pre

以题目中给出的 1->2->3->4->5->NULL 为例，反转过程如下：

反转链表图解步骤

⚠️ 需要注意的是：

为了进行下一轮遍历，在修改 next 指针前需要先保存下一个节点
反转结束后，最终要返回的节点为原链表的最后一个节点

具体实现

Python

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        while head:
            # 获取下一个节点
            next_node = head.next
            # 改变下一个节点
            head.next = pre
            # 修改 pre
            pre = head
            # 修改 head
            head = next_node
        return pre

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}