【链表】力扣206题：反转链表网站首页 技术杂谈

【链表】力扣206题：反转链表

三耳01 2023-06-11 08:00:02

简介【链表】力扣206题：反转链表

【链表】力扣206题：反转链表

力扣206题：反转链表

建议在看题目之前先了解数组的具体知识点，可以看这里：
算法基础（三）：链表知识点及题型讲解。
其它题目：
【链表】力扣203题：移除链表元素

力扣206题：反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）206

首先，我们要知道，随着不断遍历，head的位置会从第一个元素逐渐后移，所以我们首先需要定位住我们需要的位置：
然后，开始将元素不断前移。将2移到1前面，再将3移到2前面，一直到head.next为空为止：

此时我们可以看到，移动了2以后，dnext和hnext都在对应的位置上（因为在代码中，每一个循环都重新定义了一遍dnext和hnext的位置，确保分别在dummy和head后面。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 以[1,2,3,4,5]为例，一个一个移动
        dummy = ListNode(0)
        dummy.next = head  # 1前面的指针

        while head is not None and head.next is not None:
            # 定义dummy和head的下一个节点
            dnext = dummy.next
            hnext = head.next

            # 把2移到1前面
            dummy.next = hnext  # dummy指向2
            head.next = hnext.next  # 1指向3
            hnext.next = dnext  # 2指向1
            # 此时走完一轮，head还是1，则hnext = head.next表示的是3
        
        return dummy.next