剑指offer–反转链表

一、前言

最近开始刷剑指offer，记录一下。牛客网在线编程板块的剑指offer专区。 牛客网剑指offer：传送门 或者点击下方链接。 https://www.nowcoder.com/ta/coding-interviews

二、题目描述

输入一个链表，反转链表后，输出新链表的表头。

三、代码

# -*- coding:utf-8 -*- # -*- coding:utf-8 -*- class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here # 1、将现有的头换成尾，尾部的next为空 # 2、将从第二个node开始，循环将next指向前一个 # 3、需要一直有一个指针指向还没有翻转的链表的头部 if pHead==None: return None if pHead.next==None: return pHead leftPoint = pHead midPoint = pHead.next # rightPoint = pHead.next.next rightPoint = midPoint.next leftPoint.next = None while rightPoint != None: midPoint.next=leftPoint leftPoint=midPoint midPoint=rightPoint rightPoint=rightPoint.next midPoint.next = leftPoint return midPoint if __name__ == '__main__': s=Solution() l1 = ListNode(1) l2 = ListNode(2) l3 = ListNode(3) l4 = ListNode(4) l5 = ListNode(5) l1.next = l2 l2.next = l3 l3.next = l4 l4.next = l5 l5.next = None print(s.ReverseList(l1))