题解 | #反转链表#

反转链表

http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

反转链表

LeetCode206. 反转链表

问题描述

给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。
示例:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

分析问题

首先,我们按照题目的要求,先把图画出来,然后再分析。

image-20210906105355690

从图中我们可以看到,反转前和反转后指针的指向发生了反转。所以,我们在实现的过程中,我们可以通过调整链表的指针来达到反转链表的目的。

  1. 我们定义两个指针pre和cur。pre表示已反转部分的头结点,cur表示还没有反转部分的头结点。开始时cur=head,pre=None
  2. 每次让cur->next=pre,实现一次局部反转。
  3. 局部反转完成后,cur和pre同时向前移动一位。
  4. 循环上述过程,直到链表反转完成。

image-20210906143404239

代码实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverse(self, head):
        cur = head
        #初始化时,pre为None
        pre = None
        while cur:
            next=cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

head=ListNode(1,None)
cur=head
for i in range(2,6):
    tmp=ListNode(i,None)
    cur.next=tmp
    cur=cur.next

s=Solution()
pre=s.reverse(head)

while pre!=None:
    print(pre.val)
    pre=pre.next
全部评论

相关推荐

07-04 16:00
门头沟学院 Java
点赞 评论 收藏
分享
但听说转正率很低,我现在有在实习了,好纠结要不要去
熬夜脱发码农:转正率低归低,但是实习的经历你可以拿着,又不是说秋招不准备了
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务