206、翻转链表

题目

反转一个单链表。
示例:

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

答案

#
# @lc app=leetcode.cn id=206 lang=python3
#
# [206] 反转链表
#


# @lc code=start
# 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和 cur，pre指向None
        pre, cur = None, head

        while cur:
            # 保存当前节点的下一个节点
            # tmp = cur.next
            # # 然后将当前节点指向前一个节点
            # cur.next = pre
            # # 前一个节点指向当前
            # pre = cur
            # # 当前节点指向保存的下一个tmp
            # cur = tmp

            pre, cur.next, cur = cur, pre, cur.next
        return pre


# Solution().reverseList([1, 2, 3, 4, 5])

# @lc code=end

Note

双指针迭代
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 属性指向 pre（指向翻转），然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
动画演示如下：