反转链表

发表于：
字数： 267 阅读：≈ 1分钟 浏览： 评论：

题目

翻转链表，如 1 -> 2 -> 3 -> 4 ，翻转为 4 -> 3 -> 2 -> 1

思路

对于空节点（head is None）或者单节点（head.next is None），翻转后还是一样的，所以直接返回。

对于多节点的情况，如 1 -> 2，朴素的思路是创建一个假节点 dummy_node，依次遍历目标节点，被遍历到的节点指向 dummpy_node。

reverse_link.gif

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, val=0, next=None):
 4#         self.val = val
 5#         self.next = next
 6class Solution:
 7    def reverseList(self, head: ListNode) -> ListNode:
 8        if head is None or head.next is None:
 9            return head
10        
11        dummy_node = None
12		while head:
13        	next_node = head.next  # 保存当前节点的下一个节点
14        	head.next = dummy_node  # 将当前节点的 next 指向反转后的链表
15        	dummy_node = head       # 更新 dummy_node 为当前节点
16        	head = next_node       # 移动到下一个节点
17
18        return dummy_node