您现在的位置是:首页 >技术杂谈 >【链表】力扣206题:反转链表网站首页技术杂谈

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

三耳01 2023-06-11 08:00:02
简介【链表】力扣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以后,dnexthnext都在对应的位置上(因为在代码中,每一个循环都重新定义了一遍dnexthnext的位置,确保分别在dummyhead后面。
# 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

执行用时:40 ms, 在所有 Python3 提交中击败了64.05%的用户
内存消耗:16.1 MB, 在所有 Python3 提交中击败了54.84%的用户

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。